The name "common knowledge" was coined by the philosopher David Lewis in 1969, in a book about how conventions like driving on the right side of the road hold together, and the game theorist Robert Aumann made it mathematically precise in 1976. The muddy children puzzle is older than either. The mathematician J. E. Littlewood printed a version in 1953 about three ladies in a railway carriage with smudged faces, all laughing at each other, and in 2008 the mathematician Terence Tao posted it on his blog as the blue-eyed islanders puzzle, with 100 blue-eyed islanders all working it out on day 100, and hundreds of readers argued about it in the comments. The two-thirds game was invented by the economist Rosemarie Nagel, who ran it in the lab in 1995 and found most people at level 1 or level 2. In 1997 the Financial Times ran it for its readers: the average guess was 18.9, so the winning number was 13. The hats puzzle comes from Todd Ebert's 1998 doctoral thesis, and its clever plan is a tiny error-correcting code, the same mathematics that lets a scratched CD still play.
What everybody knows that everybody knows
Some children come in from the mud, and none of them can see their own forehead. A teacher says one sentence that every child already knew, and somehow that sentence lets the muddy ones work out who they are. This chapter is about the gap between everybody knowing something and everybody knowing that everybody knows it, and about how many levels deep a real person thinks before they stop.
Here is the puzzle. Some children come inside after playing in the mud. A few of them, say k, have mud on their foreheads. Every child can see every other child's forehead, but not their own. There are no mirrors, and nobody may talk, point, or make faces. The teacher looks at the whole group and announces, out loud: "At least one of you has a muddy forehead." Then she asks, "If you know you are muddy, step forward."
Nobody moves. She asks again. Nobody moves. She keeps asking, and on the kth time, every muddy child steps forward at the same moment, and no clean child does. Not one of them ever saw their own face.
Play it before you read how it works. You are one of the children, so your own forehead is a question mark. The other children are robots, and each one shows what it is thinking. Every time the teacher asks, press I stay put to let the round go by, or I step forward when you are certain. Certain is the whole game: stepping forward too early, or when you are clean, is a mistake even if you happen to be muddy. Leave the muddy count on Secret, so you have to work it out the way the children do.
The muddy children
You are one of the children. Robots reason perfectly and never peek.The star needs a secret muddy count of at least 3, and it needs you to be one of the muddy ones. The deal is random, so it can take a few games.
Now the reasoning, one muddy child at a time.
- One muddy child. She sees no mud anywhere. The teacher said somebody is muddy. So it is her, and she steps forward on round 1.
- Two muddy children. Each of them sees exactly one muddy face and thinks: "If I am clean, that child sees no mud at all and will step forward on round 1." Round 1 goes by and nobody moves. "So I am not clean." Both step forward on round 2.
- Three muddy children. Each sees two muddy faces and thinks: "If I am clean, those two are in the two-muddy situation, and they will step forward on round 2." Round 2 passes, nobody moves, and all three step forward on round 3.
Here is the pattern. A child who sees m muddy faces waits m rounds. If those m children step forward, she is clean. If they do not, she is muddy, and she steps forward on round m + 1. That rule is the entire strategy, and it is exactly what the robots above are running. A muddy child sees one fewer muddy face than a clean child does, so she acts one round earlier, and that round is round k.
Why the announcement matters
Now the puzzle inside the puzzle. Suppose k is 2 or more. Then before the teacher said a word, every child could already see at least one muddy forehead. Every child already knew "at least one of us is muddy." The teacher told them something they all knew. So how did it change anything?
Take k = 2, with Robo 1 and Robo 2 muddy. Robo 1 knows somebody is muddy: it can see Robo 2. But does Robo 1 know that Robo 2 knows? Robo 1 thinks: "If my own forehead is clean, then Robo 2 sees no mud at all, and Robo 2 has no idea anybody is muddy." Robo 1 cannot rule that out. So Robo 1 knows the fact, but does not know whether Robo 2 knows it. And the round-2 argument needs exactly that: "if I were clean, Robo 2 would have known, and would have stepped forward." Without the announcement, Robo 1 cannot make that argument, and nothing ever happens.
The teacher's sentence fixes this, not because of what it says but because of how it is said: out loud, to everyone, with everyone watching everyone else hear it. After it, everyone knows the fact, everyone knows that everyone knows it, everyone knows that everyone knows that everyone knows it, and so on without end. A fact like that is called common knowledge. Think of it as a ladder:
- Rung 1. Everyone knows it.
- Rung 2. Everyone knows that everyone knows it.
- Rung 3. Everyone knows that everyone knows that everyone knows it.
- Rungs 4, 5, 6, ... and so on, forever.
Before the announcement, the ladder for "somebody is muddy" is only k − 1 rungs high, and the round-k argument needs rung k. The announcement builds the whole ladder in one sentence. Check it below for two and for three muddy robots, before and after.
The knowledge ladder
Every robot shown is muddy. Which rungs hold?Guess two thirds of the average
Common knowledge is about what people know. The next game is about how deep they think. Everyone in a group secretly picks a whole number from 0 to 100. Then you average all the numbers, take two thirds of that average, and whoever is closest wins.
What would you pick? A first thought: "if the others pick at random, the average is about 50, and two thirds of 50 is 33." Call that level 1 thinking. A second thought: "but everybody will think that, so they will all pick 33, and two thirds of 33 is 22." That is level 2. Level 3 picks 15, level 4 picks 10, and each level assumes the crowd is exactly one level below it. Play against nine Robos. You choose how deep they think. The Mixed crowd is the realistic one: a spread from level 0 to level 3, with each Robo wobbling a couple of points, the way real people do.
Two thirds of the average
You and nine Robos. Closest to two thirds of the average wins.Reason it out
Imagine a huge crowd, so your own number hardly moves the average, and allow fractions. Cross out the numbers that can never be a best pick, one step at a time.
Push the reasoning as far as it goes. Even if every single person picks 100, the average is 100 and two thirds of it is 66.7. So a number above 66.7 can never be closer to the target than 66.7 itself. It is dominated, Chapter 2's word, and a sensible player crosses it out. But if everyone can see that, nobody picks above 66.7, so the average is at most 66.7, and two thirds of that is 44.4. Now everything above 44.4 is dominated. Cross it out and the ceiling drops to 29.6, then 19.8, then 13.2. Every step cuts the ceiling to two thirds of what it was, and the only number that survives every step is 0. That is the game's equilibrium (Chapter 3): if everyone reasons perfectly, and everyone knows that everyone reasons perfectly, all the way up the ladder, everyone picks 0.
Real crowds do not. When newspapers have run this contest with thousands of readers, the average guess landed in the twenties or thirties, and the winning number in the teens or low twenties, because most people climb two or three levels and then stop. Nobody is at level 100. So the winning move is not to reason perfectly. It is to reason exactly one level deeper than the crowd you are actually in. Try that against the mixed crowd: it takes a few rounds, because the level-0 Robos add luck, but a number near 20 wins far more often than 33 or 50.
The three hats
One more puzzle about what people can see. Three players each get a hat, red or blue, decided by a coin flip. Each sees the other two hats and not their own. At the same moment, each player must either guess their own hat color or say "pass." The team wins if at least one player guesses right and nobody guesses wrong. No talking once the hats are on, but the team may agree on a plan beforehand.
The obvious plan: one player guesses, the other two pass. A guess about your own hat is a coin flip, so the team wins half the time, and it seems as if nothing could beat that, because nobody ever sees their own hat. Here is the plan that does: if you see two hats of the same color, guess the other color; otherwise pass. Play it, then run a thousand games with each plan and compare. Then look at the table of all eight ways the hats can fall and find where the clever plan loses.
Red hat or blue hat?
You are a player. The two Robos follow the clever plan. Hat colors here are just hat colors.A thousand games
All three players are Robos in these runs. Expect about 500 and about 750.
The clever plan does not make any single guess better than a coin flip. Every guess anybody makes is still right exactly half the time. What the plan does is arrange the guesses so that the wrong ones all happen in the same two games, when the three hats match and everyone guesses wrong together, while the right ones are spread out one per game across the other six. Losses concentrated, wins spread out. Six wins out of eight is 3/4. Real error-correcting codes, the ones that let a scratched disc still play, use the same trick with more hats.
Muddy children by induction. The claim: with k muddy children, all of them step forward on round k and nobody steps forward before that. It works for k = 1: the one muddy child sees no mud, hears "at least one," and steps forward on round 1, while every clean child sees one muddy face and waits. Now suppose it works for k, and take k + 1 muddy children. Each muddy child sees k muddy faces and reasons: "If I were clean, there would be exactly k muddy children, and by the claim for k they would step forward on round k." Round k passes and nobody moves, so on round k + 1 every muddy child knows, and steps forward. A clean child sees k + 1 muddy faces and is still waiting. So it works for k + 1. It works for 1, so it works for 2, so for 3, and so on for every k.
The shrinking ceiling. If nobody picks above c, the target is at most 2/3 of c. Starting from 100:
After n steps the ceiling is 100 × (2/3)n, which never stops shrinking and gets as close to 0 as you like. One honest footnote: with whole numbers and a small group, the last step gets fuzzy. In a group of 10, "everybody picks 1" is also an equilibrium, because a lone switch to 0 pulls the target down by less than it moves you, so the switcher loses. The huge crowd with fractions lands cleanly on 0.
Hats. Three fair coins give 2 × 2 × 2 = 8 equally likely hat patterns. The clever plan loses on exactly 2 of them (all red, all blue), so it wins 6/8 = 3/4 of the time. The one-guesser plan wins 4/8 = 1/2.
Everyone knowing a fact is not the same as everyone knowing that everyone knows it, and the gap between those two can be the difference between nothing happening and everything happening. Common knowledge is a ladder with no top rung, and the only way to build the whole thing at once is to say the fact out loud to everyone together.
And when you guess what other people will do, remember that they are guessing about you, but only a few levels deep. Think one level deeper than them, not infinitely deeper.
1. There is exactly one muddy child. What happens, and on which round?
Answer
The muddy child sees no mud, and the announcement tells her it must be her. She steps forward on round 1. Every other child sees exactly one muddy face, waits through round 1, watches her step forward, and then knows they are clean.
2. Instead of announcing it, the teacher whispers "at least one of you is muddy" into each child's ear separately, so each child knows only what was whispered to them. Does anybody ever step forward?
Answer
Not when k is 2 or more. Every child already knew the fact, and a whisper adds nothing to the ladder: Robo 1 still cannot tell whether Robo 2 knows, because for all Robo 1 can tell, Robo 2 sees no mud and was told nothing. The ladder is stuck at rung k − 1, and nobody ever moves. With k = 1 the whisper is enough, because the one muddy child needs only rung 1.
3. Three players pick 0, 30, and 60. What is two thirds of the average, and who wins?
Answer
The average is 30, and two thirds of it is 20. The distances are 20, 10, and 40, so the player who picked 30 wins. Notice that 0 lost. The equilibrium number only wins when everyone else plays it too.
Two armies are camped on two hills with the enemy in the valley between them. They win only if both attack at the same moment; an army that attacks alone is destroyed. The only way to talk is a messenger who runs through the valley, and any messenger might be captured. General A sends: "Attack at dawn." Did the messenger get through? A cannot know. So B sends one back: "Got it, dawn." Now B cannot know whether that one arrived. Show that no plan with a finite number of messengers can ever make "attack at dawn" common knowledge, no matter how many of them get through.
Answer
Suppose some plan with a finite number of messages works, meaning both armies attack together whenever the plan is followed, whatever happens to the messengers. Look at the last message in the plan. Its sender cannot tell whether it arrived, so the sender does exactly the same thing either way, and since the plan works, the sender attacks whether or not that last message got through. The receiver must attack at the same moment in both cases too, so the last message never changed what anybody did. Delete it: the plan still works with one message fewer. Now delete the new last message by the same argument, and keep going until the plan has no messages at all. But a plan with no messages cannot say when to attack. So no such plan exists. Each message adds one rung to the ladder, and the ladder never reaches the top.
Computer scientists call this the two generals problem, and networks live with it every second. When one computer sends another a message, it does not wait to be certain that the other computer knows that it knows. It waits a set amount of time for a reply, and sends again if none comes. Certainty is impossible, so engineers settle for very likely, and a timer.
Stars in this chapter
Earn them by doing the clever thing, not by clicking around.
- Step forward on exactly the right round with a secret muddy count of 3 or more
- Win a round of two thirds of the average against the mixed crowd
- Say what perfect reasoners pick in the two-thirds game