RackPull

Common knowledge in the blue eyes puzzle

A popular formulation of the blue eyes logic puzzle is given on xkcd. I’m going to explain the concept of common knowledge in the context of the puzzle. If you don’t already know the solution to the puzzle, it’s not spoiled below and you can consider this page a hint.

Let P denote the proposition “I can see someone who has blue eyes.” There is common knowledge of P only when

  • every islander knows P (first-order knowledge),
  • every islander knows that every islander knows P (second-order knowledge),
  • every islander knows that every islander knows that every islander knows P (third-order knowledge),
  • and so on.

All these levels of knowledge are required for a proposition to be considered common knowledge. P is known by each of the islanders, but it is not common knowledge among them before the guru says P. Here’s an explanation of why, starting with simple cases.


Case of 1 blue-eyed islander

Suppose only 1 islander has blue eyes: Alice.

Alice doesn’t see anyone who has blue eyes. She doesn’t know P; more specifically, she doesn’t have first-order knowledge of P.

Therefore, P is not common knowledge when only 1 islander has blue eyes.


Case of 2 blue-eyed islanders

Suppose only 2 islanders have blue eyes: Alice and Bob.

Bob can see 1 person who has blue eyes, Alice. Since he doesn’t know the colour of his own eyes, he doesn’t know whether Alice can see anyone who has blue eyes. In other words, Bob doesn’t know whether Alice knows P. This is a piece of second-order knowledge that Bob is missing.

Therefore, P is not common knowledge when only 2 islanders have blue eyes.

Why is this interesting?

At this point, it should be clear that just because everyone knows something, doesn’t mean they knows that as a group, they each have that piece of knowledge. Every islander knows that they can see someone who has blue eyes, but Bob doesn’t know that every islander knows that they can see someone with blue eyes (and neither does Alice).

Perspective of a non-blue-eyed islander

Before we go on to the next case, which is more complicated, let’s first consider the perspective of an islander without blue eyes, Oscar.

  • Oscar knows that Bob can see Alice’s blue eyes, so Oscar knows that Bob knows P.
  • Likewise, Oscar knows that Alice can see Bob’s blue eyes, so Oscar knows that Alice knows P.
  • In general, Oscar knows that every islander can see Alice or Bob’s blue eyes, so Oscar knows that every islander knows P. Oscar has second-order knowledge that Alice and Bob don’t have.

Case of 3 blue-eyed islanders

Suppose only 3 islanders have blue eyes: Alice, Bob, and Carol.

Every islander can see at least 2 islanders who has blue eyes, so the reasoning from Oscar’s perspective above applies here to: Every islander knows that every other islander knows P. Every islander has the same complete second-order knowledge. Since there’s no difference between the islanders in this regard, second-order knowledge is no longer useful to us in determining whether P is common knowledge.

Intuitively, we should now consider the third-order knowledge of the islanders and see whether there’s any discrepancy. Is there a piece of third-order knowledge that some islander doesn’t have? Consider the following question:

Does Carol know whether Bob knows that Alice knows P?

This is a question about third-order knowledge from the perspective of Carol. Think about it as long as you need to, because it’s the crux of the concept of common knowledge.

  • Bob knows that Alice knows P, and the only reason is Bob knows Alice can see Carol’s blue eyes. But Carol doesn’t know the colour of her own eyes, so Carol can’t know that Bob knows Alice knows P for this reason.
  • Carol knows that Alice knows P, and the only reason is Carol knows Alice can see Bob’s blue eyes. But Carol knows Bob doesn’t know the colour of his eyes either, so Carol knows that Bob can’t know that Alice knows P for this reason.
  • Thus the answer to the question is no, Carol doesn’t know whether Bob knows that Alice knows P.

Therefore, P is not common knowledge when only 3 islanders have blue eyes.

Explanation from Carol’s perspective

If the above reasoning is too hard to understand, let’s rephrase it from Carol’s perspective:

  • I am Carol, and I see only 2 people who have blue eyes: Alice and Bob. Does Bob know whether Alice knows P?
  • I know that Alice knows P because she can see Bob’s blue eyes. But this isn’t enough for Bob to know that Alice knows P because Bob doesn’t have the information that I have, which is that he has blue eyes.
  • The only way for Bob to know that Alice knows P is if I have blue eyes as well, since Bob would then know that Alice can see my blue eyes. But I don’t know whether Bob has that information given I don’t have that information myself (whether I have blue eyes).
  • The answer is no, I don’t have enough information to tell whether Bob knows that Alice knows P.

The key here is Carol’s perspective of Bob’s perspective includes both her lack of knowledge about her own eye colour and his lack of knowledge about his own eye colour. From Carol’s perspective of Bob’s perspective, only Alice’s eyes are known to be blue. From Carol’s perspective of Bob’s perspective of Alice’s perspective, no islander’s eyes are known to be blue. There is not enough information for third-order knowledge across the three of them.

Explanation by diagrams

Here is a series of diagrams to illustrate the point:

blue eyes puzzle

Each level of knowledge combines the knowledge of the previous level. The higher the level, the less knowledge there is. The bottom diagram shows a perspective where P isn’t known. Similar diagrams can be drawn for Alice’s knowledge of Bob’s knowledge of Carol’s knowledge, etc.

Other third-order knowledge

Note that we have picked one particular piece of third-order knowledge to discuss, where P isn’t known. Although Carol doesn’t have this particular piece of third-order knowledge of P, she does have other pieces of third-order knowledge of P. For instance, Carol knows that Bob knows that Carol knows P, because they both see blue eyes in a third party, Alice. Carol also knows that every islander without blue eyes knows that Bob knows P. And so on. Furthermore, every islander without blue eyes knows that every islander knows P. The point is we need only a single instance where P isn’t known in order to show that P isn’t common knowledge.


Case of 4 blue-eyed islanders

Suppose only 4 islanders have blue eyes: Alice, Bob, Carol, and Dave.

  1. Alice knows P, because Alice can see the blue eyes of Bob, Carol, and Dave.
  2. Bob knows that Alice knows P, because Bob knows that Alice can see the blue eyes of Carol and Dave.
  3. Carol knows that Bob knows that Alice knows P, because Carol knows that Bob knows that Alice can see Dave’s blue eyes.
  4. But Dave doesn’t know whether Carol knows that Bob knows that Alice knows P, because the only reason Carol knows that Bob knows that Alice knows P is Carol knows that Bob knows that Alice can see the blue eyes of Dave (the other reason Bob has for knowing that Alice knows P, which is Carol having blue eyes, is not known to Carol), and Dave doesn’t know he himself has blue eyes.

Therefore, P is not common knowledge when only 4 islanders have blue eyes.


General case of arbitrarily many blue-eyed islanders

Suppose exactly n islanders have blue eyes: I1, I2, I3, …, In – 1, In.

I2 knows that I3 knows that I4 knows that … knows that In – 1 knows that In knows P, for precisely the following reason: They all know that In can see the blue eyes of I1. This is the sole reason for I2 knowing that. All the other possible reasons can be ruled out:

  • In being able to see the blue eyes of I2 can’t be the reason, because I2 doesn’t know whether I2 has blue eyes.
  • In being able to see the blue eyes of I3 can’t be the reason, because I2 knows that I3 doesn’t know that I3 has blue eyes.
  • In being able to see the blue eyes of In – 1 can’t be the reason, because I2 knows that In – 1 doesn’t know that In – 1 has blue eyes.

I1 does not know whether I2 knows that I3 knows that … knows that In – 1 knows that In knows P, because I1 cannot know the sole reason of In being able to see the blue eyes of I1.

Therefore, P is not common knowledge for any number of islanders with blue eyes.


Why is the guru important?

When the guru announces that she can see someone with blue eyes, that is when P becomes common knowledge among the islanders. Now every islander knows that every islander knows that every islander knows that … knows that every islander knows P, with the ultimate reason being the guru said P is true. The islanders no longer have to base their higher-order knowledge of P on whether an islander with blue eyes can see another islander with blue eyes.

For example, in the case of 3 blue-eyed islanders, Carol didn’t know whether Bob knew that Alice knew P. Now that Carol knows that Bob knows that Alice knows that the guru said P, Carol does know that Bob knows that Alice knows P.