On an island where nobody can see their own eyes, a visitor announces in front of everyone that at least one islander has blue eyes. When several islanders have blue eyes, each of them can already see a blue-eyed person, so the announcement seems to tell nobody anything new. Under the rules of the puzzle it nevertheless starts a countdown, and if islanders have blue eyes, all of them leave together on the th night. This page follows the reasoning night by night and shows that what the announcement adds is common knowledge, a fact about what everyone knows about what everyone else knows.
Key terms
Blue-eyed islanders puzzle
Definition The blue-eyed islanders puzzle is a logic puzzle about an island on which of the islanders have blue eyes and the rest have eyes of other colors. Every islander can see the eyes of every other islander but never their own. There are no mirrors, nobody ever discusses eye color, and no islander has any other source of information about their own eyes, so in particular nobody is told how many islanders have blue eyes. Every islander reasons perfectly. The island has one rule. An islander who becomes certain that their own eyes are blue leaves the island that night, and every morning everyone sees who has left. One day a visitor whom everyone trusts tells all the islanders at once, truthfully, that at least one of them has blue eyes. The rules, the perfect reasoning, the announcement and the morning observations are common knowledge among the islanders, as defined below, and nothing before the visit had made it common knowledge that someone has blue eyes. Counting the night after the announcement as night 1, nobody leaves during the first nights, and on night all blue-eyed islanders leave together. Islanders without blue eyes never leave, since nobody can become certain of something false. If an earlier public event had already made the same fact common knowledge, the count would have started from that event, and the visitor’s words would change nothing.
In plain words Every blue-eyed islander sees one fewer blue-eyed person than there really are and waits to see whether those people leave on schedule. When they do not, each concludes that they are the extra blue-eyed person. Every quiet night is a piece of public evidence, and the announcement gives everyone the same starting point for counting the nights.
Example Start with one blue-eyed islander. That islander sees no blue eyes, so the announcement can only be true if their own eyes are blue, and they leave on night 1. Everyone else can see those blue eyes, so for them the announcement settles nothing about their own eyes. Next take two blue-eyed islanders, A and B. Islander A sees that B has blue eyes and reasons that if A’s own eyes are not blue, B is the only blue-eyed islander and will leave on night 1, as in the first case. Islander B reasons the same way about A. Neither can be certain yet, so nobody leaves on night 1. In the morning A sees that B is still there. If A’s eyes were not blue, B would have left, so A’s eyes must be blue. B reaches the same conclusion, and both leave on night 2. With three blue-eyed islanders A, B and C, each sees two and thinks that if their own eyes are not blue, those two will leave on night 2. Nobody leaves on nights 1 and 2, so all three leave on night 3. The same step works for every . Suppose the claim holds when there are blue-eyed islanders, and now let there be . Each blue-eyed islander sees of them and thinks that if their own eyes are not blue, those will leave on night and not earlier. Until that night nothing happens that this possibility fails to predict, so nobody can be certain sooner. When night also passes quietly, each blue-eyed islander concludes that their own eyes are blue, and all leave on night .
Common knowledge
Definition A fact is common knowledge in a group when everyone in the group knows it, everyone knows that everyone knows it, everyone knows that everyone knows that everyone knows it, and so on for any number of repetitions. It helps to separate three levels. Individual knowledge is a fact that one person knows. Shared knowledge, also called mutual knowledge, is a fact that everyone in the group knows, which says nothing about what they know of one another. Common knowledge is the whole endless chain. In the islanders puzzle with blue-eyed islanders, the fact that at least one islander has blue eyes holds before the visit to exactly levels of “everyone knows” and not to levels. So it is shared knowledge when , but it is never common knowledge until the announcement.
In plain words Seeing a fact yourself is not the same as knowing that everyone else sees it, and that is not the same as knowing that everyone knows that everyone sees it. A fact is common knowledge when nobody has to wonder, at any depth, whether someone might be unaware of it.
Example Take three blue-eyed islanders A, B and C before the visit. Everyone knows that someone has blue eyes, since each blue-eyed islander sees two blue-eyed people and everyone else sees three. Everyone also knows that everyone knows it. For instance, A knows that B knows it, because A can see that C has blue eyes and that B can see C. The third level fails, because A does not know that B knows that C knows it. As far as A can tell, A’s own eyes might not be blue. In that case B would see only C with blue eyes, and B, unsure of B’s own eyes, would have to allow that C sees no blue eyes at all and so does not know the fact. After the announcement, every statement of this kind is true, however long the chain.
Public announcement
Definition A public announcement is a statement made to all members of a group at once, in such a way that everyone hears it, everyone knows that everyone hears it, and so on, and everyone trusts that it is true. A true fact that is announced publicly becomes common knowledge at that moment. In epistemic logic, described below, a public announcement removes every possible situation in which the statement is false, for everyone at once. Events that everyone observes together act in the same way. In the islanders puzzle each night on which nobody leaves is also public information, and it rules out every situation in which someone would have left.
In plain words A public statement does more than inform each listener. It also tells each listener that all the others heard the same thing and know that everyone heard it. Everyone can then reason about how everyone else will reason, starting from the same fact.
Example With two blue-eyed islanders A and B, the announcement tells A nothing new about eye colors, since A can see B. What it changes is A’s picture of the situation in which A’s eyes are not blue. In that situation B sees no blue eyes, and without the announcement B would have no reason to leave. After the announcement, A knows that B heard it too, so in that situation B would leave on night 1. That prediction is what makes B’s staying informative. Without any announcement nobody ever leaves, whatever is. No islander can rule out, from what they see, that their own eyes are not blue, so in no possible situation would anyone leave on night 1, and a quiet first night rules nothing out. The same holds on every later night.
Epistemic logic
Definition Epistemic logic is the logic of statements about knowledge, such as “A knows that P” and “A knows that B knows that P”. Its standard model uses possible worlds, complete descriptions of how things might be. For each person and each world, the model lists the worlds that this person cannot tell apart from it with the information they have. A person knows a statement in a world when the statement is true in every world that person cannot tell apart from it. In the islanders puzzle a world says which islanders have blue eyes and which do not, so with islanders there are worlds, and an islander cannot tell apart two worlds that differ only in that islander’s own eyes. A public announcement or a publicly observed event deletes every world that does not fit it, and knowledge is then judged among the worlds that remain.
In plain words To know something is to be sure of it in every situation you cannot rule out. Each piece of public information shortens the list of situations that everyone can still imagine, and a person learns a fact when every situation left on their list agrees on it.
Example Take two islanders A and B, both blue-eyed, and describe a world by two letters, b for blue eyes and o for other eyes, first for A and then for B. The four worlds are bb, bo, ob and oo, and the real world is bb. Islander A cannot tell bb from ob, and B cannot tell bb from bo. The announcement deletes oo. In the world bo, islander A could only confuse it with oo, which is gone, so in bo islander A would know and would leave on night 1. In the same way, in ob islander B would leave on night 1. In the real world nobody leaves on night 1, and that public fact deletes bo and ob. Only bb remains, so both islanders know that their eyes are blue, and they leave on night 2. With more islanders the model has more worlds, but each quiet night deletes them in the same way, the worlds with one blue-eyed islander after night 1, those with two after night 2, and so on.
Check yourself
- Change the number. The island has five blue-eyed islanders and ten islanders whose eyes are not blue. Who leaves, and on which night? What does an islander without blue eyes expect, and what does that islander learn?
Show the answer
The five blue-eyed islanders leave together on night 5, and nobody leaves on nights 1 to 4. Each of them sees four blue-eyed people and thinks that if their own eyes are not blue, those four will leave on night 4. When nobody leaves on night 4, each concludes that their own eyes are blue.
An islander without blue eyes sees five blue-eyed people. If that islander’s eyes were blue, there would be six, and all six would leave on night 6. If not, the five would leave on night 5. When the five leave on night 5, each of the ten learns that their own eyes are not blue. They still stay, because the rule only sends away islanders who are certain that their eyes are blue.
- Change the announcement. With blue-eyed islanders, the visitor says instead that at least two islanders have blue eyes. When do the blue-eyed islanders leave?
Show the answer
They leave on night . The smallest case is now two blue-eyed islanders. Each of them sees exactly one blue-eyed person, and the announcement can only be true if their own eyes are blue, so both leave on night 1. With three, each sees two and expects them to leave on night 1 if their own eyes are not blue. When nobody leaves on night 1, all three leave on night 2. Each additional blue-eyed islander adds one night, so of them leave on night . The stronger announcement deletes more worlds at the start, all those with zero or one blue-eyed islander, so the countdown has one step fewer to go.
- Find the missing knowledge. Three islanders A, B and C have blue eyes, and the visitor has not yet come. Give a statement about knowledge that is false before the announcement and true after it.
Show the answer
One such statement is “A knows that B knows that C knows that at least one islander has blue eyes.” Before the visit, A has to allow that A’s own eyes are not blue. In that case B sees only C with blue eyes, and B in turn has to allow that B’s eyes are not blue, in which case C would see no blue eyes. So among the worlds A must consider, there is one in which B cannot be sure that C knows the fact, and the statement is false. The shorter statements are true, since everyone knows the fact and everyone knows that everyone knows it.
After the announcement the fact is common knowledge, so this statement and every longer chain are true. The missing third level is exactly what the three-night argument uses. Each blue-eyed islander considers a world with two blue-eyed islanders, each of those considers a world with one, and the lone blue-eyed islander in that world must have heard the announcement for the argument to start.