The following is an exercise from the book: Reasoning about Knowledge by R.Fagin, J.Y. Halpern, Y. Moses, M.Y. Vardi.
I have been trying for some time to crack it but still unable to find a simple approach to solve it. Any suggestions are appereciated.
Consider a game which is played with a deck consisting of four aces and four eights. There are three players. Six cards are dealt out, two to each player. The remaining two cards are left face down. Without looking at the cards, each of the players raises them up to his or her forehead, so that the other two players can see
them but he or she cannot. Then all of the players take turns trying to determine which cards they’re holding (they do not have to name the suits). If a player does not know which cards he or she is holding, the player must say so. Of course, it is common knowledge that none of you would ever lie, and that all players are perfect reasoners.
Show that there exists a situation where only one of the players will be able to determine what cards he or she holds, and the other two will never be able to determine what cards they hold, no matter
how many rounds are played.
It is relatively simple to see that at least one player will detarmine her/his own cards the as it seems key cases are:
$AA,88,A8$ – third player determines his/her cards since first and second players can nonot determine theyr cards $AA,88$ are impossible.
$A8,88,A8$ – first player determines his/her own cards on second move.
$A8,A8,A8$ – second player determines his/her cards on second move.
All other cases are reducible to the three to see that at least one will determine his/her cards at some move.
But I can not find the case when the remaining two can not determine their cards in any number of moves. I don't see a structure which gives this.
It seems that $A8,88,A8$ and $A8,AA,A8$ are such situations that second and third player can not decide which cards they have, am I right?
Can players 1 and 2 distinguish $AA,88,A8$ from $AA, AA, 88$?
Best Answer
This is a tricky question. Partly because of the fact that the order in which people speak does make a difference.
Here's a solution.
First of all note that player three will never be able to figure out that she has two aces (because a game where she has two eights is completely symmetrical; nothing can ever make her distinguish between these two options).
The game develops as follows.
Round 1:
At the end of round 1, everyone knows there must be at least one mixed pair. And in fact, it is common knowledge that there is at least one mixed pair. (if there is no mixed pair, someone figures out their cards in round 1)
Round 2:
Player 1 says "I don't know".
Now player 2 knows that player 1 sees at least one mixed pair! So... player 2 says "I know". Crucially (and this is where Jaap's answer breaks): Player 1 does not know why player 2 knows that she has a mixed pair. As far as Player 1 is concerned, this could be
Round 3:
I think that at this point, player 1 still does not have enough information to conclude her mixed pair. The reason is: if you play the first six steps of a game where player 1 has 88, player 2 has A8 and player 3 has AA, the result is exactly the same.
etcetera.