But does he know that I know that he knows? December 25, 2010Posted by Ezra Resnick in Game theory, Puzzles.
Five children have been playing together, and three of them have gotten mud on their foreheads. Each child can see mud on others but not on himself. When the children come home, their father says that at least one of them has mud on his forehead; he then asks if anyone can deduce whether there is mud on his own forehead. The children look around, but no one answers. So the father asks again: Does anyone know whether he has mud on his own forehead? Silence. The father then repeats his question a third time, at which point all three dirty children immediately step forward and proclaim that their foreheads must be muddy.
The first (and simplest) puzzle is: How did the kids know? And why did the father have to ask three times?
The solution is inductive: begin by considering what would happen if there were only one muddy child, Alex. He would see that all the others are clean, so when the father states that at least one child is dirty, Alex would immediately know it must be him. Therefore, if there were only one dirty child, he would come forward after the father’s first query. Next, suppose there are two muddy children, Alex and Bob. Alex sees that Bob is dirty, and vice versa. As far as Alex knows, Bob could be the only dirty one, and as far as Bob knows, Alex could be the only dirty one; so neither of them step forward after the father’s first query (each expecting the other to do so). However, when Alex sees that Bob did not immediately come forward, and since we already concluded that if there were only one muddy child he would have identified himself right away, Alex can deduce that his own forehead must be muddy as well. Bob reasons likewise, and so they both step forward when the father asks a second time. Applying the same logic to our original scenario shows that the three dirty children can identify themselves as soon as they see that no one came forward after the second query — so in this case, the third time is the charm.
A more interesting puzzle, however, is this: Was the father’s opening statement that “at least one child has mud on his forehead” necessary? Reexamining the solution above, we find that the “base case” in which there is only one muddy child doesn’t work without the father’s statement — the dirty child would never come forward, since as far as he knows, no one is muddy. Consequently, the entire chain of inference collapses. So the father’s statement is necessary — but this seems paradoxical, since he merely told the children something they already know! After all, if there are three muddy foreheads, each of the five children knows just by looking at the others that “at least one child has mud on his forehead.” So what information does the father’s statement actually provide?
Think again about the case where only two children have mud on their foreheads, Alex and Bob, and let p represent the statement “at least one child has mud on his forehead.” It is then true that each of the five children knows p even without the father saying so, but the problem is that not everyone knows that everyone else knows p: as far as Alex knows, Bob could be the only muddy one, in which case Bob would not know that “at least one child is muddy” (since Bob would see only clean faces). Likewise, as far as Bob knows, Alex might not know p. This is what prevents them from deducing their own situation. What about our original case? When there are three dirty children, not only does everyone already know p, everyone knows that everyone knows p. However, not everyone knows that everyone knows that everyone knows p! What the father provides, then, is common knowledge: after his statement, they all know that there is at least one muddy child, and they all know that they all know it, and they all know that they all know that they all know it…
A closely related scenario is the coordinated attack problem. Suppose that two generals, each in command of an army division, wish to launch a surprise attack on the enemy. However, the only way for the attack to succeed is if both divisions attack simultaneously; if a single division attacks alone it will be defeated. Unfortunately, the only way for the generals to communicate is by messenger, and the messengers can be lost or delayed along the way. What should the generals do? Suppose that general A sends general B the message: “Attack at dawn on January 1st.” This is certainly not enough to guarantee a coordinated attack, since general A cannot be sure that his message was received. So let’s say that general A waits until he receives a confirmation message back from general B. Can both generals then attack with confidence? No, since general B doesn’t know whether the confirmation he sent was received by general A — and general B knows that general A will not attack without receiving that confirmation. (And general A knows that general B knows this.) So even though both generals know when to attack, and they each know that the other knows, they cannot attack because neither general knows that the other knows that he knows!
This situation is familiar to anyone trying to make an appointment with someone by email. How many rounds of confirmation are necessary to be sure you both know the engagement is on? It’s easy to see that no number of acknowledgments and counter-acknowledgments will allow the parties to achieve absolute certainty. As explained in a paper by Ronald Fagin, Joseph Halpern, Yoram Moses and Moshe Vardi, guaranteeing coordinated attack requires common knowledge, and common knowledge cannot be achieved where communication is not guaranteed. Actually, the situation is worse than that: even in a system where communication is guaranteed, if there is any uncertainty about the delivery time — e.g., even if all messages are guaranteed to arrive in one millisecond or less — common knowledge is impossible to achieve.
Fagin et al. go on to explore various ways out of this apparent stalemate. But if you ever miss a date, you can always claim that you didn’t show up because the other party didn’t acknowledge your acknowledgment of their acknowledgment…