The following simple game has one solution that seems correct, but isn’t. Can you figure out why?
The Game
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.]
B,X2,0
B,Y2,2
C,X0,1
C,Y6,0
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.)
Vs gur nobir nanylfvf jrer pbeerpg Cynlre Gjb jbhyq oryvrir ur jvyy arire zbir. Fb jung unccraf vs Cynlre Gjb qbrf trg gb zbir? Vs Cynlre Gjb trgf gb zbir jung fubhyq uvf oryvrs or nobhg jung Cynlre Bar qvq tvira gung Cynlre Gjb xabjf Cynlre Bar qvq abg cvpx N? Cynlre Gjb pna’g nffhzr gung P jnf cynlrq. Vs vg jrer gehr gung vg’f pbzzba xabjyrqtr gung Cynlre Bar jbhyq arire cynl O, gura vg fubhyq or pbzzba xabjyrqtr gung Cynlre Gjb jbhyq arire cynl L, juvpu jbhyq zrna gung Cynlre Bar jbhyq arire cynl P, ohg pyrneyl Cynlre Bar unf cvpxrq O be P fb fbzrguvat vf jebat.
Zber nofgenpgyl, vs V qrirybc n gurbel gung lbh jba’g gnxr npgvba Y, naq guvf arprffnevyl erfhygf va gur vzcyvpngvba gung lbh jba’g qb npgvba Z, gura vs lbh unir pyrneyl qbar rvgure Y be Z zl bevtvany gurbel vf vainyvq. V’z abg nyybjrq gb nffhzr gung lbh zhfg unir qbar Z whfg orpnhfr zl vavgvny cebbs ubyqvat gung lbh jba’g qb Y gbbx srjre fgrcf guna zl cebbs sbe jul lbh jba’g qb Z qvq.
Abar vs guvf jbhyq or n ceboyrz vs vg jrer veengvbany sbe Cynlre Bar gb abg cvpx N. Nsgre nyy, V unir nffhzrq engvbanyvgl fb V’z abg nyybjrq gb cbfghyngr gung Cynlre Bar jvyy qb fbzrguvat veengvbany. Ohg vg’f veengvbany sbe Cynlre Bar gb Cvpx P bayl vs ur rfgvzngrf gung gur cebonovyvgl bs Cynlre Gjb erfcbaqvat jvgu L vf fhssvpvragyl ybj. Cynlre Gjb’f zbir jvyy qrcraq ba uvf oryvrsf bs jung Cynlre Bar unf qbar vs Cynlre Bar unf abg cvpxrq N. Pbafrdhragyl, jr pna bayl fnl vg vf veengvbany sbe Cynlre Bar gb abg cvpx N nsgre jr unir svtherq bhg jung oryvrs Cynlre Gjb jbhyq unir vs Cynlre Gjb trgf gb cynl. Naq guvf oryvrs bs Cynlre Gjb pna’g or onfrq ba gur nffhzcgvba gung Cynlre Bar jvyy arire cvpx O orpnhfr guvf erfhygf va Cynlre Gjb oryvrivat gung Cynlre Bar jvyy arire cvpx P rvgure, ohg pyrneyl vs Cynlre Gjb trgf gb zbir rvgure O be P unf orra cvpxrq.
Va fhz, gb svaq n fbyhgvba sbe gur tnzr jr arrq gb xabj jung Cynlre Gjb jbhyq qb vs ur trgf gb zbir, ohg gur bayl ernfbanoyr pnaqvqngr fbyhgvba unf Cynlre Gjb arire zbivat fb jr unir n pbagenqvpgvba naq V unir ab vqrn jung gur evtug nafjre vf. Guvf vf n trareny ceboyrz va tnzr gurbel jurer n fbyhgvba erdhverf svthevat bhg jung n cynlre jbhyq qb vs ur trgf gb zbir, ohg nyy gur ernfbanoyr fbyhgvbaf unir guvf cynlre arire zbivat.
Update: Emile has a great answer if you assume a “trembling hand.”
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?
The Game
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.]
B,X 2,0
B,Y 2,2
C,X 0,1
C,Y 6,0
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.)
http://rot13.com/
Vs gur nobir nanylfvf jrer pbeerpg Cynlre Gjb jbhyq oryvrir ur jvyy arire zbir. Fb jung unccraf vs Cynlre Gjb qbrf trg gb zbir? Vs Cynlre Gjb trgf gb zbir jung fubhyq uvf oryvrs or nobhg jung Cynlre Bar qvq tvira gung Cynlre Gjb xabjf Cynlre Bar qvq abg cvpx N? Cynlre Gjb pna’g nffhzr gung P jnf cynlrq. Vs vg jrer gehr gung vg’f pbzzba xabjyrqtr gung Cynlre Bar jbhyq arire cynl O, gura vg fubhyq or pbzzba xabjyrqtr gung Cynlre Gjb jbhyq arire cynl L, juvpu jbhyq zrna gung Cynlre Bar jbhyq arire cynl P, ohg pyrneyl Cynlre Bar unf cvpxrq O be P fb fbzrguvat vf jebat.
Zber nofgenpgyl, vs V qrirybc n gurbel gung lbh jba’g gnxr npgvba Y, naq guvf arprffnevyl erfhygf va gur vzcyvpngvba gung lbh jba’g qb npgvba Z, gura vs lbh unir pyrneyl qbar rvgure Y be Z zl bevtvany gurbel vf vainyvq. V’z abg nyybjrq gb nffhzr gung lbh zhfg unir qbar Z whfg orpnhfr zl vavgvny cebbs ubyqvat gung lbh jba’g qb Y gbbx srjre fgrcf guna zl cebbs sbe jul lbh jba’g qb Z qvq.
Abar vs guvf jbhyq or n ceboyrz vs vg jrer veengvbany sbe Cynlre Bar gb abg cvpx N. Nsgre nyy, V unir nffhzrq engvbanyvgl fb V’z abg nyybjrq gb cbfghyngr gung Cynlre Bar jvyy qb fbzrguvat veengvbany. Ohg vg’f veengvbany sbe Cynlre Bar gb Cvpx P bayl vs ur rfgvzngrf gung gur cebonovyvgl bs Cynlre Gjb erfcbaqvat jvgu L vf fhssvpvragyl ybj. Cynlre Gjb’f zbir jvyy qrcraq ba uvf oryvrsf bs jung Cynlre Bar unf qbar vs Cynlre Bar unf abg cvpxrq N. Pbafrdhragyl, jr pna bayl fnl vg vf veengvbany sbe Cynlre Bar gb abg cvpx N nsgre jr unir svtherq bhg jung oryvrs Cynlre Gjb jbhyq unir vs Cynlre Gjb trgf gb cynl. Naq guvf oryvrs bs Cynlre Gjb pna’g or onfrq ba gur nffhzcgvba gung Cynlre Bar jvyy arire cvpx O orpnhfr guvf erfhygf va Cynlre Gjb oryvrivat gung Cynlre Bar jvyy arire cvpx P rvgure, ohg pyrneyl vs Cynlre Gjb trgf gb zbir rvgure O be P unf orra cvpxrq.
Va fhz, gb svaq n fbyhgvba sbe gur tnzr jr arrq gb xabj jung Cynlre Gjb jbhyq qb vs ur trgf gb zbir, ohg gur bayl ernfbanoyr pnaqvqngr fbyhgvba unf Cynlre Gjb arire zbivat fb jr unir n pbagenqvpgvba naq V unir ab vqrn jung gur evtug nafjre vf. Guvf vf n trareny ceboyrz va tnzr gurbel jurer n fbyhgvba erdhverf svthevat bhg jung n cynlre jbhyq qb vs ur trgf gb zbir, ohg nyy gur ernfbanoyr fbyhgvbaf unir guvf cynlre arire zbivat.
Update: Emile has a great answer if you assume a “trembling hand.”