The study of competitive and non-competitive games, equilibrium concepts such as Nash equilibrium, and related subjects. Combinatorial games such as Nim are under (combinatorial-game-theory), and algorithmic aspects (e.g. auctions) are under (algorithmic-game-theory).

learn more… | top users | synonyms

2
votes
1answer
72 views

game strategy question

Let's say there are doors each with a lock on the integral points ($0$, $\pm1$, $\pm2$, $\cdots$) of the line. You are given a key which can only open a single lock, but you are not told what lock the ...
8
votes
1answer
146 views

Feedback loop in real-time voting of TV show?

Today, a German TV casting show ("Unser Star Fur Baku") introduced a new "real-time" voting system that works as follows: 10 contestants take part in a song competition. Viewers can call in and vote ...
1
vote
2answers
99 views

Why must a preference relation for an agent be over a set of alternatives for which they can choose from instead of any set?

A preference relation is of course a reflexive, total and transitive binary relation on a set, with the additional requirement that the agent be able to select one alternative from the set. I don't ...
1
vote
1answer
757 views

Finding Nash equilibria using Support Enumeration

Chapter 3 of the Book "Algorithmic Game Theory" introduces an algorithm (page 8 of that PDF) to find mixed Nash equilibria for a bimatrix game $(A, B)$, which I struggle to understand. ($M$ and $N$ ...
0
votes
1answer
221 views

Payoff of a unilateral deviation in an $n$-player zero-sum game

In a $n$-player zero-sum game, one of the players, say $k$, unilaterally deviates from her Nash equilibrium strategy while all the other players stay on the equilibrium. Now, we all know that $k$'s ...
1
vote
1answer
110 views

What is the strategy the winner must employ to ensure victory?

Tushar and Gaurav once won a competition and were given a single Dairy Milk Chocolate Bar as the first prize. Little kids as they were, they started fighting over sharing it. Finally they decided to ...
2
votes
1answer
147 views

strategy gambling money game

Two players, A and B, are each given 10000 dollars. They'll play a 10 round game. In each round both have to gamble some of this money (can be zero); in the 10th round, they both must use all their ...
0
votes
1answer
3k views

Optimal Mixed Strategies?

I'm trying to understand how I would find the optimal mixed strategies in zero sum games. For example... given the following zero sum game in standard strategic form... \begin{array}{r|r|} +8 ...
8
votes
3answers
236 views

Markov Perfect Equilibrium with Incomplete Information

Since the pathbreaking paper Stochastic Games (1953) by Shapley, people have analyzed stochastic games and their deterministic counterpart, dynamic games, by examining Markov Perfect Equilibria, ...
2
votes
1answer
89 views

Game Theory Moving Around Coins

To start off, we have coins arranged in the following order: ..C.. A F.. D.. B ..E.. G The goal of this game is to return these letters into alphabetical order: A, B then C, D, E then F, G in the ...
5
votes
2answers
681 views

Modified pirate game

The pirate game is a popular problem that is often asked in interviews (which is how I stumbled upon it). The problem asks There are 5 rational pirates, A, B, C, D and E. They find 100 gold coins. ...
3
votes
1answer
518 views

what resources would help someone understand Game Theory proofs?

Please note that my knowledge of math proofs is little to none. I was wondering what resources, free or paid, would allow me to understand the math proofs specifically related to Game Theory? I ...
5
votes
1answer
28 views

Mechanism to auction off multiple resources given fixed budgets

I am trying to sell ad time on a screen to a bunch of advertisers. The advertisers tell me (or a salesperson keys in) how much a given advertiser is willing to pay for time in a one hour block. Each ...
2
votes
1answer
96 views

the name of a game

I saw a two-player game described the other day and I was just wondering if it had an official name. The game is played as follows: You start with an $m \times n$ grid, and on each node of the grid ...
4
votes
3answers
2k views

Game Theory - Unsure how to proceed with this question

A company has a competition to win a car. Each contestant needs to pick a positive integer. If there’s at least one unique choice, the person who made the smallest unique choice wins the car. If there ...
8
votes
4answers
354 views

Probability question: optimal strategy

I am really confused about how to think about this question. It was presented as a challenge by a peer. Two people seek to kill a duck at a location $Y$ meters from their origin. They walk from ...
3
votes
1answer
524 views

Proving that some mixed strategy is a mixed Nash Equilibrium

Inspired by the bar room scene from A Beautiful Mind (link), as an extra assignment for a Game Theory course we were asked to analyze this scene. We assume there are $n \geq 2$ men, an equal amount of ...
22
votes
7answers
5k views

Game theory - self study

I want to self study game theory. Which math-related qualifications should I have? And can you recommend any books? Where do I have to begin?
7
votes
1answer
305 views

Optimal strategy for slice weighing game

I watched an interesting contest on a Swedish game show the other night. I have tried to find an english name of the contest but haven't found any. Two contestants were each given one large sausage ...
1
vote
0answers
182 views

Optimal Mixed Strategies for Latin Square Games

From Ferguson's Game Theory: A Latin square is an $n \times n$ array of $n$ different letters such that each letter occurs once and only once in each row and each column. Such games have simple ...
8
votes
0answers
468 views

Irreversible chess [closed]

Suppose we play a chess-variant, where any finite number of pieces are allowed, and the board is as large as we wish, but only two kings in total. And there is no 50 move-rule, no castling and no ...
2
votes
1answer
347 views

A checkerboard problem

If $mn$ squares out of a $2m\times n$ white checkerboard are colored black, and a move consists of interchanging the color on any two squares who share a side, how many moves at maximum can it take to ...
0
votes
1answer
324 views

Game Theory-Rationalizable Strategies [duplicate]

Possible Duplicate: Set of rationalizable strategies Consider a guessing game with ten players, numbered $1$ through $10$. Simultaneously and independently, the players select integers ...
10
votes
1answer
139 views

What are the relevant properties of cardinal utility functions for defining a notion of expected utility for mixed strategies in games?

For (finite) normal form games we can develop everything for pure strategies by considering ordinal utility functions to capture only a players preferences over the pure strategy space of the game. ...
3
votes
1answer
401 views

Nash equilibrium question

(Hotelling’s voting model) Consider a population of voters uniformly distributed along the ideological spectrum from left (x = 0) to right (x = 1). There are two candidates i = 1,2 for a single office ...
2
votes
2answers
208 views

Mixed strategy nash equilibria in from $2\times N$ bimatrix form

I'm looking for a way of finding (manually!) mixed strategy Nash equilibria in a $2\times N$ game. Calling player 1 the player with two strategies and player 2 the one with $N$ strategies, I've ...
2
votes
1answer
143 views

Cournot game and Bertrand game: Are they classes of game?

Can we use the term "Cournot Game" to describe a competition with output quantity in general? Or, does "Cournot Game" only refer to the game studied by Cournot? For example, if we study a dynamic ...
16
votes
3answers
2k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
0
votes
1answer
632 views

Number of pure strategies for each player in a simple game

I've just started following a game theory course. I'm still getting used to the concepts so I hope I can get some comment on my thoughts. This is a homework exercise. Consider a four square board. ...
0
votes
2answers
115 views

Does selecting more boxes initially change the math of “Deal or no Deal”?

Apologies if this seems to duplicate questions 835 and 886, but I think it's a different question... In Deal or No Deal the contestant selects one of 26 boxes and then chooses boxes in groups of 6, ...
0
votes
1answer
207 views

Apply game theory/Nash equilibrium in computer security scenario

I want to apply the game theory to a scenario in security . where two ppl the optimal outcome of a game is one where no player has an incentive to deviate from his or her chosen strategy after ...
1
vote
1answer
137 views

Can this problem be approached with Game Theory?

Hallo all, I would like some insight on this one: There are two players A and B each having a countable set of naturals lets say Sa and Sb. Initially Sa has cardinality n and Sb has cardinality 0 ...
1
vote
1answer
169 views

Term for a fully connected balanced graph (Rock paper scissor)

Is there a mathematical, graph theory, game theory term for a graph that is fully connected and balanced evenly with each other node. I'm thinking in situations like Rock paper scissors where each ...
1
vote
1answer
112 views

Reducing an infinitely large matrix to a finite matrix using domination

I'd very much appreciate it if anyone with any familiarity of game theory could help out a newbie. I came across the following problem doing homework in an introductory game theory course: ...
7
votes
3answers
2k views

Secretary problem - why is the optimal solution optimal?

I have read about this problem: http://en.wikipedia.org/wiki/Secretary_problem But I want to see how it is proven that the "optimal" solution is indeed optimal. I understand how to prove that if the ...
15
votes
7answers
1k views

Game theory textbooks/lectures/etc

I looking for good books/lecture notes/etc to learn game theory. I do not fear the math, so I'm not looking for a "non-mathematical intro" or something like that. Any suggestions are welcome. Just put ...
1
vote
1answer
90 views

Nonhedonic coalitional game vs. hedonic coalitional game

What is the difference between nonhedonic and hedonic coalitional games?
7
votes
5answers
376 views

Good non-mathematician book on Game Theory

I'm looking for a good book on Game Theory. I run a software company and from the little I've heard about Game Theory, it seems interesting and potentially useful. I've looked on Amazon.com but ...
2
votes
2answers
551 views

How to calculate perceived value?

Is there a known formula to calculate perceived value? If I am auctioning some popular product that is worth $100 (shelf price), how much would people bid if they: Have a 1 in ...
0
votes
1answer
46 views

Standardize heuristic values

I'm currently writing a reversi AI. What it does is, it looks a few moves ahead and then evaluates the boards and gives them scores, depending on how good it is. I use a few methods for evaluating ...
2
votes
1answer
210 views

Nash equilibrium and common knowledge

If NE is a CK? It seems that yes since given all information about payoffs/strategies players can derive NE based on the procedures similar to that of in the common knowledge, but I'm not sure.
8
votes
1answer
332 views

Common knowledge as a fixed point

I read on a wikipedia page that from the modal logic formalization CK can be formulated as a fixed point. If it also holds for the set theory formalization? If it does, where I can find about it? ...
4
votes
2answers
345 views

Cooperative Game Theory specialized forum

I am looking for research-focused Game Theory forum, especially in Cooperative Game Theory. As it sometimes happen google provides links on either conferences (as opposed to online forums) or forums ...
2
votes
2answers
341 views

calculate dominant mixed strategy in two person game w/ finite strategies

For a two person game, player one has strategies A,B,C. Inspection reveals strategy B is strictly dominated by some mixture between A and C. How does one calculate the probabilities assigned to A ...
3
votes
1answer
490 views

Game about placing pennies on table

This problem is from The Art and Craft of problem solving book: Consider the following two player game. Each player takes turns placing a penny on the surface of a rectangular table. No penny can ...
18
votes
1answer
1k views

Number of moves to solve a flood-it/sock-dye game

[ Question based on the sock dye game ] [ Update: It appears that this game is better known as "Flood it" and is NP-hard. Also, "the number of moves required to flood the whole board is $\Omega(n)$ ...
4
votes
1answer
230 views

Meaning of a partial derivative here?

I am given a 'tariff' function for two countries, $i=1, 2$. Both players can select a tariff between 0 and 100. If player $i$ selects $x_i$ and player $j$ selects $x_j$, country $i$ gets a payoff of ...
5
votes
1answer
415 views

Finding Nash equilibrium aka finding where lines intersect

I am tagging this as multivariable calculus because it potentially involves taking partial derivatives. I am working on some mathematical treatment for Cournot duopoly models (not homework, just ...
5
votes
1answer
265 views

Algebraically finding a Nash equilibrium

Here's the problem that relates to a whole class of problems to which I am trying to figure out a general solution. Given two players 1 and 2 who can select a number from the interval $[0, 1]$, ...
3
votes
1answer
532 views

Set of rationalizable strategies

Consider a guessing game with ten players, numbered 1 through 10. Simultaneously and independently, the players select integers between 0 and 10. Thus player i's strategy space is $\mathbf{S}_i$ $=$ ...