Blind Man's Bluff: Formalizing theory-of-mind reasoning in a classic model of common knowledge
There are many variations of a classic example from game theory for differentiating knowledge and common knowledge. We revisit that example in the form of the "Blind Man's Bluff" game, which involves three players reasoning about the color (red or black) of a playing card they drew. Each player holds their card on their forehead to reveal it to the others but conceal it from themself. They reason about their own card based on the actions chosen by the others after a helpful announcement from a trustworthy friend. The primary mandate of the game is that a player will announce that their card is red upon deducing that fact with certainty, and thereby win the game. Suppose each card is red (the true state of the world). No player knows the color of their own card, and so none can yet win, but each player does possess the knowledge that not every card is black. However, only after their friend announces "not every card is black"—making that private knowledge common knowledge— does it become certain that at least one player will deduce their own card is red and, consequently, announce that fact to win the game. In this game, we formalize the Theory-of-Mind (ToM) reasoning in- volved in refining each player's possibility partition, which describes the sets of states of the world that are indistinguishable to them given the available information, following the friend's initial announcement and the subsequent action choices. We focus on how the refinement process does not require knowledge of any specific announcement or action—only common knowledge of the sequential information revelation process. Our framework applies the concept of a "rough approximation" (from Rough Set theory). We find that the upper approximation of a player's possibility partition defined by another player's possibility partition has a clear ToM interpretation, though the meaning of the lower approximation is less obvious. We also consider the role of strategies, which map a player's information to a choice of action, and contrast the perception- based strategies used in the game with inference-based ones. To deal with common knowledge about strategies, we construct a modified, but informationally-equivalent game that involves repeated announcements from the friend instead of sequential action choices by the players. In this way—via a common knowledge device—our framework decouples, for the first time, the recursive ToM reasoning process from the information revelation process in a multi-stage game of incomplete information.