Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The game is the following: player1 is hiding the coin in his hand and the player2 has to guess where is the coin. If he guesses that it is in the right hand of the player1, he obtains €2 (player1 looses €2). If player2 guesses that the coin in the left hand then he obtains €1 (player1 looses €1). If player2 didn't guess he gives €2 to player1 if the coin was in the right hand or €1 if the coin was in the left hand.

Suppose you are a player1.

1) You know that if the player2 guesses that the coin in your right hand, the player2 will have the maximal profit - then it's optimal to you to hide the coin in the left hand.

2) You know that the player2 can follow the same logic - and then he will come to the fact that you will hide the coin in the left hand and guess about your strategy. So on this step of thinking you will decide to "cheat" player's2 thoughts and hide a coin in the right hand.

...

You can make your decision on the optimality of the player2, but then you can assume that he will follow the same logic and hence will make another decision - and for this game the loop will never finish.

If this phenomena is described in the game theory and how is it called?

share|improve this question
6  
Yes, one says that there is no pure strategy Nash equilibrium, that is, there are no pure strategies for the players that form a Nash equilibrium. There is, however, always a mixed strategy Nash equilibrium in a two-player zero-sum game. These terms are all explained at Wikipedia. –  joriki Apr 6 '11 at 12:35
    
If you write it as an answer, I will accept. –  Ilya Apr 7 '11 at 8:02
1  
By the way, in this game, the Nash equilibrium is to hide the coin twice as often in the left hand, and to guess the left hand twice as often as the right. –  Douglas Zare Apr 7 '11 at 9:40
    
But you didn't announce that you'd unaccept it one and a half years later ;-) (rightly so, I like Michael's answer). –  joriki Nov 30 '12 at 18:27
    
@joriki oh, my bad - I just seen that Michael answered the question and accepted his answer, as I forgotten that your answer was already accepted. I didn't expect that another answer would be automatically dis accepted. I fixed it, so your answer now is accepted and I will grant Michael a bounty. Sorry for this situation, I thought mse will tell me that I am dis accepting another answer –  Ilya Nov 30 '12 at 19:25

3 Answers 3

up vote 5 down vote accepted

Yes, one says that there is no pure strategy Nash equilibrium, that is, there are no pure strategies for the players that form a Nash equilibrium. There is, however, always a mixed strategy Nash equilibrium in a two-player zero-sum game. These terms are all explained at Wikipedia.

share|improve this answer
    
wiki is a little bit non-formal. could you advise smth useful for me who never studied the game theory but has a good background in math? –  Ilya Apr 7 '11 at 9:44
    
I'm sorry, no, I can't; I didn't learn any of that formally. –  joriki Apr 7 '11 at 9:55

In a 1935 paper on economic prediction, Oskar Morgenstern posed the following problem:

Sherlock Holmes, pursued by his opponent, Moriarty, leaves London for Dover. The train stops at a station on the way, and he alights there rather than travelling on to Dover. He has seen Moriarity at the railway station, recognizes that he is very clever and expects that Moriarity will take a faster special train in order to catch him in Dover. Holmes' anticipation turns out to be correct. But what if Moriarity had been still more clever, had estimated Holmes' mental abilities better and had foreseen his actions accordingly? Then, obviously, he would have travelled to the intermediate station. Holmes, again, would have had to calculate that, and he himself would have decided to go on to Dover. Whereupon, Moriarity would again have "reacted" differently. [...] One may be easily convinced that there lies an insoluble paradox.

The conclusion Morgenstern drew was that prediction is essentially impossible in economics. Later he met John von Neumann, who has written a paper on parlor games in 1928 in which he proved the minmax theorem: In every finite two-player zero-sum game (such as the one in the question), there exists a pair of strategies and a number $v$ such that one players strategy guarantees here a minimum payoff of $v$ and the other player has a strategy that guarantees here a minimum payoff of $-v$. These guarantees are independent of what the other players do. Since it is a zero-sum game, nobody can do better either, so this pair of strategies form what would later be known as a Nash equilibrium. The proof relied on two things: Players can use randomized strategies and players evaluate their payoff by taking expectations. Morgenster and von Neumann then collaborated and the rest is history.

There is a conceptual problem with randomized strategies, the mixed strategies. If you play two pure strategies $s$ and $s'$ both with positive probability, but $s$ gives a higher payoff than $s'$, then you could gain in expectation by increasing the probability of $s$ and reducing the probability of $s'$. So rational people only randomize when they cannot gain by randomization.

There is a solution to this problem that is now quite popular among game theorists and is championed by Robert Aumann. In his view, players do not really randomize. The randomizing is done in the head of the other players. Holmes doesn't have to believe that Moriarty is randomizing, he just has to form an probabilistic assesment of what Moriarty is doing. Under this view, Nash equilibrium can be interpreted as a profile of assesment satisfying certain conditions: For each player, all other players have the same assesment of her strategies. Nobody would be forced to change their assesment upon hearing the assesment of the others.

share|improve this answer
    
It appeared that I dis accepted eventually the answer by joriki. To be fair, I fixed it, and I will give a bounty to your answer as soon as mse allows me doing it - is it ok? Sorry for this mess –  Ilya Nov 30 '12 at 19:26
    
No problem. And you dn't have to give me a bounty. –  Michael Greinecker Dec 1 '12 at 12:45
    
The answer certainly deserves it –  Ilya Dec 1 '12 at 17:31
1  
@Ilya Thank you very much!! –  Michael Greinecker Dec 3 '12 at 8:43

Shameless Advertisement: Game Theory proposal on Area 51 that you should totally follow!

This is called the matching pennies game.

\begin{vmatrix} \ \color{blue}{P_1},\color{green}{P_2}& \color{green}{Left} & \color{green}{Right} & \color{green}{Give\space Up} \\ \ \color{blue}{Left} & \color{blue}{-1},\space\space\space\color{green}{1} & \space\space\space\color{blue}{2},\color{green}{-2} & \color{blue}{1},\color{green}{-1} \\ \ \color{blue}{Right} & \space\space\space\color{blue}{1},\color{green}{-1} & \color{blue}{-2},\space\space\space\color{green}{2} & \color{blue}{2},\color{green}{-2} \end{vmatrix}

The strategy Give Up appears to be a strictly dominated strategy; that is, player $P_2$ should never play it.

You correctly identified that there are no particular strategy each player should reliably play (which would constitute a pure strategy equilibrium). Instead, players should randomize between Left and Right. This is called a mixed stategy, and allows people to choose a probability distribution over possible actions.

The mathematician/game theorist Nash proved that every finite game has an equilibrium, though that depends on the existence of mixed strategies, like in this game. However, there is experimental evidence showing that people are poor randomizers except under certain conditions. There is also a YouTube video on this game if you'd like to learn more.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.