Glossary / Common knowledge
Two generals stand on two hills with the enemy in the valley between them. Together they win, alone they die. They can agree only through messengers, and a messenger can be caught. The generals swap confirmations: "got it", "got your 'got it'"… It seems that after a dozen such notes no doubt would be left. Yet even a thousand confirmations don't give them what they really need.
“In plain words” is hidden on all puzzles.
General A sends a messenger: "We attack at dawn". General B replies with his own messenger: "Got it". A replies: "Got your 'got it'". And so on, taking turns. The enemy can catch any messenger, and then the sender never finds out.
After how many delivered messengers can a general attack and be certain he won't be fighting alone?
Try it yourself. Messengers run back and forth until one of them is caught. Each general attacks if he has received at least k messengers addressed to him. Pick k and the chance that the enemy catches a messenger, and play thousands of nights.
General A is on the left, B on the right, time runs downwards. A dashed arrow with a cross is a captured messenger, where the exchange ends. The number by an arrow is how many "knows that" the chain already holds.
However many messengers the plan has, someone sends the last one and doesn't know whether it arrived. Finding out needs one more confirmation, and that brings the same trouble. So demanding "more confirmations" doesn't help: it only makes a joint attack rarer. And on the nights when a general does go into battle, the risk of being alone stays the same as the chance of losing a single messenger.
Each delivered messenger adds one "knows that" to the chain. The first: B knows the plan. The second: A knows that B knows. The third: B knows that A knows that B knows. But the generals need all of these floors built at once, without end. That is what is called common knowledge, and messengers never deliver it.
Three friends are bored at a party. Each will leave only if the group leaves: standing at the door alone is awkward. You know a taxi is waiting outside. How do you get the news across so that they leave together? Try whispering to each of them separately, and then just say it out loud.
A fact is common knowledge in a group if everyone knows it, everyone knows that everyone knows it, everyone knows that everyone knows that everyone knows, and so on without end. It sounds like wordplay, but the difference is very practical. When people have to act together and nobody wants to go first, it isn't enough that each of them knows. Each must be sure that the others are sure too.
The simplest way to create common knowledge is to say something in public, where everyone sees that everyone hears. A chain of private messages, however long, can't replace that.
“Rigorous” is hidden on all puzzles.
Each person knows the fact but may think the others don't. Say each colleague was told separately that tomorrow is a holiday. Will someone still come to work tomorrow "just in case", because they aren't sure about the others?
The same thing was announced at an all-hands meeting. Nobody heard a new fact, but now everyone knows that everyone knows, and that everyone knows that too. Everyone stays home.
The classic example is Andersen's tale "The Emperor's New Clothes" (1837). Everyone in the crowd sees that the emperor is naked but keeps quiet: what if the others can see the clothes? A child shouts what everybody could already see. He reports nothing new, yet after his words everyone knows the others see it too, and the crowd laughs together.
It seems a thousand floors of "knows that" is almost infinity, and people should behave almost as if the knowledge were common. In 1989 the economist Ariel Rubinstein showed this is not so. In his "electronic mail game" two players' computers automatically send confirmations back and forth until some message gets lost. For rational players the outcome is the same as if there had been no e-mails at all: however many confirmations arrive, neither takes the risk.
You can see why in the generals' simulation. General B has received exactly k messengers, and nobody else has come. Perhaps his own reply was caught, and then A also has k messengers and attacks. Or perhaps the messenger A should have sent next was caught, and then A has received only k − 1 and waits. Both are almost equally likely, so right at the threshold general B is guessing, as if tossing a coin.
P(B alone | B received exactly k) = 1 / (2 − p)
Here p is the chance of losing a messenger. With p = 10% that is 1/1.9 ≈ 52.6%, a little worse than a coin, and it doesn't depend on k. Play some nights in the simulation above, and your numbers will appear here.
Rubinstein proved that the equilibrium is built out of such "coins": if it isn't worth the risk at the threshold, it isn't worth it one step higher either, and then one more step, and so on up to any number of e-mails.
“Deeper” is hidden on all puzzles.
E¹φ = "everyone knows φ", Ek+1φ = E(Ekφ), Cφ = E¹φ ∧ E²φ ∧ E³φ ∧ …
Ekφ is k floors of "everyone knows that". Common knowledge Cφ requires all floors at once. It can also be defined without an infinite series, as a fixed point: Cφ is equivalent to E(φ ∧ Cφ). That is, a fact is common knowledge when everyone knows both the fact and that it is common knowledge. That is exactly how a public statement works: on hearing it, everyone knows that all the others heard it together with them.
In the language of possible worlds Aumann described it like this: an event is common knowledge if it holds in every world reachable by any chain of "what if he thinks that…".
P(exactly n messengers delivered) = (1 − p)n · p
B receives the odd-numbered messengers, A the even ones. Under the rule "attack after k" B attacks once at least 2k − 1 messengers are delivered, and A once at least 2k are. Hence:
together = (1 − p)2k · alone = p · (1 − p)2k−1 · alone, given someone attacked = p
The last share doesn't depend on k at all. A larger k only lowers the chance of attacking in the first place: with p = 10% and k = 10 the generals attack together on only 12.2% of nights, while the risk for whoever goes into battle stays at 10%. For it to vanish, k would have to be infinite, which means the generals would need common knowledge.
An option that gives a player more than any other option of theirs, whatever the others choose.
A discount pays a coffee shop whatever the shop next door does, yet when both cut, each earns three times less than if both had kept their price.
A set of strategies where nobody gains by changing their own while the others keep theirs.
In the prisoner's dilemma both betray, though both would be better off silent: an equilibrium is not the best outcome.
Solving a game from the end: the last move first, then the one before it, back to the first.
In the centipede game logic says grab the pennies on the very first move, though playing on would give both of them hundreds, and real people almost never do it.