A simple game that has no solution
The following simple game has one solution that seems correct, but isn’t. Can you figure out why?
Player One moves first. He must pick A, B, or C. If Player One picks A the game ends and Player Two does nothing. If Player One picks B or C, Player Two will be told that Player One picked B or C, but will not be told which of these two strategies Player One picked, Player Two must then pick X or Y, and then the game ends. The following shows the Players’ payoffs for each possible outcome. Player One’s payoff is listed first.
A 3,0 [And Player Two never got to move.]
The players are rational, each player cares only about maximizing his own payoff, the players can’t communicate, they play the game only once, this game is all that will ever matter to them, and all of this plus the payoffs and the game structure is common knowledge.
Guess what will happen. Imagine you are really playing the game and decide what you would do as either Player One, or as Player Two if you have been told that you will get to move. To figure out what you would do you must formulate a belief about what the other player has/will do, and this will in part be based on your belief about his belief of what you have/will do.
An Incorrect Argument for A
If Player One picks A he gets 3, whereas if he picks B he gets 2 regardless of what Player Two does. Consequently, Player One should never pick B. If Player One picks C he might get 0 or 6 so we can’t rule out Player One picking C, at least without first figuring out what Player Two will do.
Player Two should assume that Player One will never pick B. Consequently, if Player Two gets to move he should assume that C was played and therefore Player Two should respond with X. If Player One believes that Player Two will, if given the chance to move, pick X, then Player One is best off picking A. In conclusion, Player One will pick A and Player Two will never get to move.
Why the Game Has No Solution
I believe that the above logic is wrong, and indeed the game has no solution. My reasoning is given in rot13. (Copy what is below and paste at this link to convert to English.)
If the above analysis were correct Player Two would believe he will never move. So what happens if Player Two does get to move? If Player Two gets to move what should his belief be about what Player One did given that Player Two knows Player One did not pick A? Player Two can’t assume that C was played. If it were true that it’s common knowledge that Player One would never play B, then it should be common knowledge that Player Two would never play Y, which would mean that Player One would never play C, but clearly Player One has picked B or C so something is wrong.
More abstractly, if I develop a theory that you won’t take action L, and this necessarily results in the implication that you won’t do action M, then if you have clearly done either L or M my original theory is invalid. I’m not allowed to assume that you must have done M just because my initial proof holding that you won’t do L took fewer steps than my proof for why you won’t do M did.
None if this would be a problem if it were irrational for Player One to not pick A. After all, I have assumed rationality so I’m not allowed to postulate that Player One will do something irrational. But it’s irrational for Player One to Pick C only if he estimates that the probability of Player Two responding with Y is sufficiently low. Player Two’s move will depend on his beliefs of what Player One has done if Player One has not picked A. Consequently, we can only say it is irrational for Player One to not pick A after we have figured out what belief Player Two would have if Player Two gets to play. And this belief of Player Two can’t be based on the assumption that Player One will never pick B because this results in Player Two believing that Player One will never pick C either, but clearly if Player Two gets to move either B or C has been picked.
In sum, to find a solution for the game we need to know what Player Two would do if he gets to move, but the only reasonable candidate solution has Player Two never moving so we have a contradiction and I have no idea what the right answer is. This is a general problem in game theory where a solution requires figuring out what a player would do if he gets to move, but all the reasonable solutions have this player never moving.
Update: Emile has a great answer if you assume a “trembling hand.”