A simple game that has no solution

The fol­low­ing sim­ple game has one solu­tion that seems cor­rect, 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 noth­ing. 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 strate­gies Player One picked, Player Two must then pick X or Y, and then the game ends. The fol­low­ing shows the Play­ers’ pay­offs for each pos­si­ble out­come. Player One’s pay­off 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 play­ers are ra­tio­nal, each player cares only about max­i­miz­ing his own pay­off, the play­ers can’t com­mu­ni­cate, they play the game only once, this game is all that will ever mat­ter to them, and all of this plus the pay­offs and the game struc­ture is com­mon knowl­edge.

Guess what will hap­pen. Imag­ine you are re­ally play­ing the game and de­cide what you would do as ei­ther 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 for­mu­late a be­lief about what the other player has/​will do, and this will in part be based on your be­lief about his be­lief of what you have/​will do.

An In­cor­rect Ar­gu­ment for A

If Player One picks A he gets 3, whereas if he picks B he gets 2 re­gard­less of what Player Two does. Con­se­quently, 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 pick­ing C, at least with­out first figur­ing out what Player Two will do.

Player Two should as­sume that Player One will never pick B. Con­se­quently, if Player Two gets to move he should as­sume that C was played and there­fore Player Two should re­spond with X. If Player One be­lieves that Player Two will, if given the chance to move, pick X, then Player One is best off pick­ing A. In con­clu­sion, Player One will pick A and Player Two will never get to move.

Why the Game Has No Solution

I be­lieve that the above logic is wrong, and in­deed the game has no solu­tion. My rea­son­ing is given in rot13. (Copy what is be­low and paste at this link to con­vert to English.)

http://​​rot13.com/​​

If the above anal­y­sis were cor­rect Player Two would be­lieve he will never move. So what hap­pens if Player Two does get to move? If Player Two gets to move what should his be­lief be about what Player One did given that Player Two knows Player One did not pick A? Player Two can’t as­sume that C was played. If it were true that it’s com­mon knowl­edge that Player One would never play B, then it should be com­mon knowl­edge 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 some­thing is wrong.

More ab­stractly, if I de­velop a the­ory that you won’t take ac­tion L, and this nec­es­sar­ily re­sults in the im­pli­ca­tion that you won’t do ac­tion M, then if you have clearly done ei­ther L or M my origi­nal the­ory is in­valid. I’m not al­lowed to as­sume that you must have done M just be­cause my ini­tial proof hold­ing 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 prob­lem if it were ir­ra­tional for Player One to not pick A. After all, I have as­sumed ra­tio­nal­ity so I’m not al­lowed to pos­tu­late that Player One will do some­thing ir­ra­tional. But it’s ir­ra­tional for Player One to Pick C only if he es­ti­mates that the prob­a­bil­ity of Player Two re­spond­ing with Y is suffi­ciently low. Player Two’s move will de­pend on his be­liefs of what Player One has done if Player One has not picked A. Con­se­quently, we can only say it is ir­ra­tional for Player One to not pick A af­ter we have figured out what be­lief Player Two would have if Player Two gets to play. And this be­lief of Player Two can’t be based on the as­sump­tion that Player One will never pick B be­cause this re­sults in Player Two be­liev­ing that Player One will never pick C ei­ther, but clearly if Player Two gets to move ei­ther B or C has been picked.

In sum, to find a solu­tion for the game we need to know what Player Two would do if he gets to move, but the only rea­son­able can­di­date solu­tion has Player Two never mov­ing so we have a con­tra­dic­tion and I have no idea what the right an­swer is. This is a gen­eral prob­lem in game the­ory where a solu­tion re­quires figur­ing out what a player would do if he gets to move, but all the rea­son­able solu­tions have this player never mov­ing.

Up­date: Emile has a great an­swer if you as­sume a “trem­bling hand.”