Aces and eights game

Question

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$?

Answer 1

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.

• Player one: Mixed pair
• Player two: mixed pair
• Player three: double-ace

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:

• Player 1 says "I don't know" (because the only way she could have known is if there were two identical pairs)
• Player 2 says "I don't know" (roughly the same reason)
• Player 3 says "I don't know" (always)

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

  • because Player 2 is the only one with a mixed pair, and player 2 figured this out after the first round.
  • or because of the actual reason and player 2 only figured this out after the first answer in the second round

• Player 3 says "I don't know" (always)

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.

• So player 1 says "Don't know" again
• So does player 3 (always)

etcetera.

Answer 2

[EDIT: The simplification I apply below fundamentally alters the game, so cannot really tell us anything about the original game. See BartBog's answer for why.]

I agree with you.

It is easier to amend the game slightly, so that in a round all three players reveal their pronouncement at the same time, independent of one another. This simplifies the reasoning because it is no longer turn based, so the order of the players no longer matters.

I think that this version is equivalent in the sense that in the end the same conclusions will be reached by the players. If you compare a single round of this version with one round around the table of the original, the players have less information to base their deductions on, so this version is at least as hard for the players as the original. On the other hand, comparing a single player's turn of the original to one round of the new version shows that more information is revealed in the new version, so the original is at least as hard as the new one. I'm not totally convinced that reasoning is valid (Edit:- It isn't!) , but for now lets assume it is.

In this simultaneous-play version of the game, deductions will be as follows:

Round 1: If all players have a pair (AA or 88), then one player will see four the same cards and know their hand. If that happens, the other two players will be able to deduce their hand and announce it in the next round.
If no one deduces their hand, this round eliminates the no-mixed-hand cases AA/AA/88 and AA/88/88.

Round 2: If any player sees two pairs (AA and 88), then they will know they have a mixed pair (A8). If that happens, the other two players will be able to deduce their hand and announce it in the next round.
If no one deduces their hand, this round eliminates the one-mixed-hand case AA/88/A8.

Round 3: If a player sees one pair (AA/A8 or 88/A8), then they will know they have a mixed hand (A8). If that happens it will be to two players, but the player with the matched pair will not know whether he has AA or 88.
If no one deduces their hand, this round eliminates the two-mixed-hand cases AA/A8/A8 and 88/A8/A8.

Round 4: Now everyone knows it must be the three-mixed-hand case A8/A8/A8, and all players deduce their hand.

So at worst one player cannot deduce their hand because they see A8/A8 and can have either AA or 88.