(Adapted from Fagin+al:1995.) Consider a game played
with a deck of just 8 cards, 4 aces and 4 kings. The three players,
Alice, Bob, and Carlos, are dealt two cards each. Without looking at
them, they place the cards on their foreheads so that the other players
can see them. Then the players take turns either announcing that they
know what cards are on their own forehead, thereby winning the game, or
saying “I don’t know.” Everyone knows the players are truthful and are
perfect at reasoning about beliefs.
-
Game 1. Alice and Bob have both said “I don’t know.” Carlos sees that Alice has two aces (A-A) and Bob has two kings (K-K). What should Carlos say? (Hint: consider all three possible cases for Carlos: A-A, K-K, A-K.)
-
Describe each step of Game 1 using the notation of modal logic.
-
Game 2. Carlos, Alice, and Bob all said “I don’t know” on their first turn. Alice holds K-K and Bob holds A-K. What should Carlos say on his second turn?
-
Game 3. Alice, Carlos, and Bob all say “I don’t know” on their first turn, as does Alice on her second turn. Alice and Bob both hold A-K. What should Carlos say?
-
Prove that there will always be a winner to this game.