There are 10 incredibly smart boys at school: A, B, C, D, E, F, G, H, I and Sam. They run into class laughing at 8:58 am, just two minutes before the playtime ends and are stopped by a stern looking teacher: Mr. Rabbit.
Mr. Rabbit sees that A, B, C, and D have mud on their faces. He, being a teacher who thinks that his viewpoint is always correct and acts only to enforce rules rather than thinking about the world that should be, lashes out at the poor kids.
“Silence!”, he shouts. “Nobody will talk. All of you who have mud on your faces, get out of the class!”. The kids look at each other. Each kid could see whether the other kids had mud on their faces, but could not see his own face. Nobody goes out of the class.
“I said, all of you who have mud on your faces, get out of the class!”
Still, nobody leaves. After trying 5 more times, the bell rings at 9 and Mr. Rabbit exasperatedly yells: “I can clearly see that at least one of you kids has mud on his face!”.
The kids’ grin, knowing that their ordeal will be over soon. Sure enough, after a few more times bawling of “All of you who have mud on your faces, get out of the class!”, A, B, C, and D walk out of the class.
Explain how A, B, C, and D knew that they had mud on their faces. What made the kids grin? Everybody knew that there was at least one kid with mud on his face. Support with a logical statement that a kid did not know before Mr. Rabbit’s exasperated yell at 9, but that the kid knew right after it.
After Mr. Rabbit’s first shout, they understood that at least one boy has mud on his face. So, if it was exactly one boy, then the boy would know that he had mud on his face and go out after one shouting.
Since nobody went out after one shouting, they understood that at least two boys have mud on their faces. If it were exactly two boys, those boys would know (they would see only one other’s muddy face and they’d understand their face is muddy too) and go out after the next shouting.
Since nobody went out after the second shouting, it means there are at least three muddy faces And so on, after the fourth shouting, A, B, C, and D would go out of the class.
This explanation does leave some questions open. Everybody knew at least three others had mud on their faces, why did they have to wait for Mr. Rabbit’s shout in the first place? Why did they have to go through the all four shoutings after that as well?
In multi-agent reasoning, an important concept arises from common knowledge. Everybody knows that there are at least three muddy faces but they cannot act together on that information without knowing that everybody else knows that too. And that everybody knows that everybody knows that and so on. This is what we’ll be analyzing. It requires some imagination, so be prepared.
A knows that B, C, and D have mud on their faces. A does not know if B knows that three people have mud on their faces. A knows that B knows that two people have mud on their faces. But A can’t expect people to act on that information because A does not know if B knows that C knows that there are two people with mud on their faces. If you think this is all uselessly complicated, consider this:
A can imagine a world in which he does not have mud on his face. (Call this world A) In A’s world, A can imagine B having a world where both A and B do not have mud on their faces. (Call this world AB)
A can imagine a world where B imagines that C imagines that D imagines that nobody has mud on their faces. (Call this world ABCD). So when Mr. Rabbit shouted initially, it could have been that nobody was going out because a world ABCD was possible in which nobody should be going out anyway.
So here’s a statement that changes after Mr. Rabbit’s yell. World ABCD is not possible i.e. A cannot imagine a world where B imagines that C imagines that D imagines that nobody has mud on their faces. So now in world ABC, D knows he has mud on his face. And in world ABD, C knows he has mud on his face and so on.