Blue Eyes and Common Knowledge

Blue Eyes is a widely-known logic puzzle, popularised by Randall Munroe (among others):

Standard logic puzzle rules apply: the islanders are perfect logicians, can't discuss eye colours, can't discern their own eye colours in reflections, et cetera. The problem is difficult and the solution is extremely counter-intuitive to many. If you have not seen it before, I encourage you to stop reading now, and try it yourself.

 

The blue-eyed islanders all leave $100$ nights after the announcement. To see this, let's consider some simpler problems.

1. Suppose only one islander has blue eyes. He sees no other islanders with blue eyes, so when the Guru announces that she sees someone who has blue eyes, that islander knows it must be himself. He leaves on that night.
2. Suppose two islanders have blue eyes. Each sees another islander with blue eyes; as far as each of them knows, the Guru is talking about the other; nobody leaves on the first night. But both of them know the solution to the one-blue-eyed-islander problem, and observe on the first night that the blue-eyed islander they see is still there. Each of them concludes that that blue-eyed islander must see somebody else with blue-eyes; they don't see anybody else fitting that description, so it must be themselves. They both leave on the second night.
3. Suppose three islanders have blue eyes. Each sees two others with blue eyes, but when neither of them leave on the second night, they know that those other islanders must each be able to see two others with blue eyes, one of whom must be themselves. They all leave on the third night.

An inductive argument shows that if the number of blue-eyed islanders is $n$, then they all leave on the $n$th night.

 

What makes this so counter-intuitive is that the Guru apparently tells the islanders something they already knew, but after the announcement they make logical deductions they could not have made before. Even after seeing the solution, it is tempting to think that the islanders have by some trick managed to agree (without communicating) on a strategy "if you can only see $d-1$ blue-eyed islanders on the $d$th day, say your eyes are blue and leave the island", and the strategy only works because they're all following it. Perhaps the only thing stopping the islanders from performing this feat sooner is that they need to know which day is the "first" day. The content of the Guru's announcement seems to be irrelevant; it could be "I see somebody with two feet", "I like table tennis", or "$2 + 2 = 5$", because the announcement only serves to synchronise the counting.

This is a popular interpretation, but it is a mistake. For example, there's no particular reason the brown-eyed islanders couldn't also count synchronously even though the announcement didn't contain the word "brown", so shouldn't they leave too? Unfortunately, this does not explain why it is a mistake; in my opinion, the real puzzle here is not "who leaves the island, and on what night?" but Blue Eyes Redux:

1. What do the islanders know after the Guru's announcement that they didn't know before?
2. How do they use this knowledge?
3. Why does it take $100$ days? What do they know on, e.g., the $50$th day, that they didn't know on the $49$th?

 

To answer this we need to inspect the reasoning used by each islander to eventually conclude that their own eyes are blue. Let's introduce some notation: for an islander $x$ and $k,d \in \mathbb{N}$,

• Let $B(x)$ be the proposition "$x$ has blue eyes".
• Let $E(k)$ be the proposition "There are at least $k$ blue-eyed islanders".
• Let $S(x,k)$ be the proposition "$x$ sees at least $k$ blue-eyed islanders".
• Let $L(x,d)$ be the proposition "$x$ leaves the island on the $d$th night".
• Let $\newcommand\knows[1][]{\mathrel{\smash{\overset{\,#1}{\Rule{0ex}{.5ex}{0ex}\smash{\leftarrow}}}}} x \knows P$ mean "$x$ knows that the proposition $P$ is true", and $x \knows[d] P$ mean "$x$ knows on the $d$th day that $P$ is true". $\newcommand\nknows[1][]{\mathrel{\smash{\overset{\,#1}{\Rule{0ex}{.7ex}{0ex}\smash{\not\leftarrow}}}}} x \nknows[d] P$ means "$x$ doesn't know on the $d$th day that $P$ is true".

For example, $x \knows B(x)$ means "$x$ knows his own eyes are blue", and $x \knows E(k)$ means "$x$ knows there are at least $k$ blue-eyed islanders", which is not quite the same as $S(x,k)$. Of course, the former is a simple inference from the latter. Let's write some rules of inference: $\newcommand\infer{\vDash} P \infer Q$ means "$Q$ can be inferred from $P$".

• Visibility: $B(x), \, x \ne y \infer y \knows B(x)$. If $x$'s eyes are blue then other islanders can see this.
• Counting: $S(x,k) \infer x \knows E(k)$. $x$ can count: if he sees at least $k$ blue-eyed islanders, then he knows there are at least $k$ blue-eyed islanders.
• Exit: $x \knows[d] B(x) \infer L(x,d)$. $x$ leaves the island as soon as he knows his own eyes are blue.
• Non-exit: $x \nknows[d] B(x) \infer \neg L(x,d)$. The inverse of Exit: $x$ does not leave the island if he doesn't know his own eyes are blue.
• Presence: $\neg L(x,d) \infer x \nknows[d] B(x)$. The contrapositive of Exit: if $x$ has not left the island, then he doesn't yet know his eyes are blue.
• Addition: $B(x), \, S(x,k) \infer E(k+1)$. If $x$'s eyes are blue and he sees at least $k$ other blue-eyed islanders, then there are at least $k+1$.
• Subtraction: $S(x,k) \infer x \knows S(y,k-1)$. If $x$ sees at least $k$ blue-eyed islanders, then he knows that another islander $y$ can see at least $k-1$.
• Discovery: $x \knows[d] E(k), \, \neg S(x,k) \infer x \knows[d] B(x)$. If $x$ knows there are at least $k$ blue-eyed islanders, but he cannot see $k$, then $x$ knows his own eyes are blue.
• Non-discovery: $x \knows[d] E(k), \, x \nknows[d] B(x) \infer S(x,k)$. A contrapositive of Discovery: if $x$ knows there are at least $k$ blue-eyed islanders, and does not know his own eyes are blue, then he must be able to see $k$.
• Deduction: $(\{P_i\} \infer Q), \, \forall i \bullet x \knows[d] P_i \infer x \knows[d] Q$. The islanders are perfect logicians: if an argument is valid and $x$ knows its premises to be true, then $x$ knows its conclusion to be true.
• Correctness: $x \knows[d] P \infer P$. The islanders do not make incorrect inferences; if they know something to be true, then it is true.
• We assume that if the true number of islanders is $n$ then $B(x) \infer S(x,n-1), \, \neg S(x,n)$, as blue-eyed islanders can see everyone's eyes except their own.

It goes without saying that $x \knows P \infer x \knows[d] P$, and $x \knows[d] P, \, e > d \infer x \knows[e] P$.

 

Let's try using this notation to analyse the problem for small numbers of islanders.

1. Suppose only one islander $x$ has blue eyes.
   • The Guru announces $E(1)$, and $x$ hears the announcement, so $x \knows E(1)$.
   • By assumption, $\neg S(x,1)$.
   • By Discovery, we infer $x \knows B(x)$ immediately. By Exit, $x$ leaves on the first night.
2. Suppose two islanders $x, y$ have blue eyes.
   • The Guru announces $E(1)$, but we already have $x \knows E(1)$ by Counting. However, $x$ knows $y$ hears the announcement, so $x \knows y \knows E(1)$.
   • By assumption, $\neg S(x,2)$, but $x \nknows[1] E(2)$ so we cannot apply Discovery. So by Non-exit $\neg L(x,1)$, and by symmetry $\neg L(y,1)$.
   • It is now the second day. $x$ observes that $y$ did not leave, so $x \knows[2] \neg L(y,1)$. By Presence and Deduction, $x \knows[2] y \nknows[1] B(y)$.
   • We have $x \knows y \knows E(1)$ and $x \knows[2] y \nknows[1] B(y)$, so by Non-discovery and Deduction, $x \knows[2] S(y,1)$.
   • So $x \knows[2] S(y,1)$ and by Visibility $x \knows B(y)$. By Addition and Deduction, $x \knows[2] E(2)$.
   • We have $x \knows[2] E(2)$ and $\neg S(x,2)$, so by Discovery $x \knows[2] B(x)$.
   • By Exit, $x$ leaves the island on the second night, and by symmetry, so does $y$.

With two blue-eyed islanders we're already able to explicitly write down something $x$ knows after the Guru's announcement that he doesn't know before: $x \knows y \knows E(1)$. Without the announcement, $y \knows E(1)$ but $x \nknows y \knows E(1)$, as $x$ doesn't see any blue-eyed islander which he knows $y$ can see.

The fundamental distinction here is between knowing something, and being able to attribute that knowledge to somebody else. For example, if you happen to know that a particular berry is poisonous, you will not eat it. Someone else might also know the berry is poisonous, but if you're unaware of that then you might worry that they would eat it. "The berry is poisonous" can't be used as a premise when you "put yourself in their shoes", because you don't know that they're aware of it. If, however, it's common knowledge that the berry is poisonous, you know they're aware of it, so you can use it as a premise while you're walking in their shoes.

 

3. Suppose three islanders $x,y,z$ have blue eyes.
   • The Guru announces $E(1)$ but not only did we already have e.g. $x \knows E(2)$ by Counting, we had e.g. $x \knows y \knows E(1)$ by Counting, Subtraction and Deduction. However, we do now have e.g. $x \knows y \knows z \knows E(1)$.

Each islander not only knows that the other islanders were present for the announcement, but they know that every other islander also knows this. "Everyone knows everyone knows everyone knows there's a blue-eyed islander" is the key information required to make the deductions which eventually lead to the islanders leaving. Although the Guru tells the islanders something they clearly already know, $x$ did not previously know that $y$ knew $z$ knew $E(1)$: $x$ can see a blue-eyed islander visible to $y$, but he does not know that $y$ sees a blue-eyed islander visible to $z$.

This is probably where it gets too abstract to follow intuitively. We're used to the idea of "walking in someone else's shoes" - but not imagining what it would be like to be someone else themselves walking in someone else's shoes. That would be like wearing two pairs of other people's shoes one over the other, which is silly. But what allows the islanders to leave, is that the Guru's announcement $E(1)$ is common knowledge, so however many pairs of shoes you're wearing one over the other, you can still use $E(1)$ as a premise. Informally, $P$ is common knowledge if

• Everyone knows $P$, and
• Everyone knows that $P$ is common knowledge.

Of course, this is self-referential, so it doesn't really work as a definition.

 

To go further, it will be useful to extend our notation. The difference between $\forall x \bullet x \knows[d] P$ and $\forall x,y \bullet x \knows[d] y \knows[d] P$ is clearly important; let's write $1 \knows[d] P$ and $2 \knows[d] P$ for these cases, and more generally $m \knows[d] P$ to mean an $m$-islander-long "chain" of knowledge about knowledge about knowledge, $\forall x_1,\ldots,x_m \bullet x_1 \knows[d] \ldots \knows[d] x_m \knows[d] P$.

• We can see that $m \knows[d] n \knows[d] P$ is equivalent to $(m+n) \knows[d] P$.
• By Correctness, $m \knows[d] P \infer (m-1) \knows[d] P$, and inductively $m \knows[d] P, \, n < m \infer n \knows[d] P$.
• Deduction can be inductively extended to $(\{P_i\} \infer Q), \, \forall i \bullet m \knows[d] P_i \infer m \knows[d] Q$. Let's call this Metadeduction.

In the problem with three blue-eyed islanders, for example, we have $2 \knows E(1)$ before the Guru's announcement and $3 \knows E(1)$ after the announcement. In fact, we have $\forall m \bullet m \knows E(1)$, although we don't use this fact for $m > 3$. This leads to a reasonable definition of common knowledge:

• $P$ is common knowledge if $\forall m \bullet m \knows P$.

Let's write this as $\infty \knows P$. There are a few more rules:

• The Guru's announcement is public: $\infer \infty \knows E(1)$. It's common knowledge that there is a blue-eyed islander.
• Remaining on the island is public: $\neg L(x,d-1) \infer \infty \knows[d] \neg L(x,d-1)$. If an islander doesn't leave the island, this becomes common knowledge the next day.
• Infinite Metadeduction: $(\{P_i\} \infer Q), \, \forall i \bullet \infty \knows[d] P_i \infer \infty \knows[d] Q$. That is, if an argument is valid and its premises are common knowledge, then its conclusion is also common knowledge. This follows directly from Metadeduction.

 

We can now answer Blue Eyes Redux:

14. Suppose there are $n$ blue-eyed islanders. ($n=100$, for example.)
    • The Guru announces $E(1)$. By many applications of Counting, Subtraction and Deduction, we previously had $(n-1) \knows E(1)$. By The Guru's announcement is public, we now have $n \knows E(1)$: this answers part A.
    • By Non-exit, $\forall x \bullet \neg L(x,1)$.
    • Remaining on the island is public so $n \knows[2] \forall x \bullet \neg L(x,1)$, and by Presence and Metadeduction we have $n \knows[2] \forall x \bullet x \nknows[1] B(x)$. By Non-discovery and Metadeduction $(n-1) \knows[2] \forall x \bullet S(x,1)$. By Visibility, Addition and Metadeduction $(n-1) \knows[2] E(2)$.
    • By Non-exit, $\forall x \bullet \neg L(x,2)$.
    • $\ldots$
    • On the $d$th day, Remaining on the island is public so $(n-d+2) \knows[d] \forall x \bullet \neg L(x,d-1)$, and by Presence and Metadeduction we have $(n-d+2) \knows[d] \forall x \bullet x \nknows[d-1] B(x)$. By Non-discovery and Metadeduction $(n-d+1) \knows[d] \forall x \bullet S(x,d-1)$. By Visibility, Addition and Metadeduction $(n-d+1) \knows[d] E(d)$. This answers part C.
    • $\ldots$
    • So $1 \knows[n] E(n)$, by assumption $\forall x \mathrel{|} B(x) \bullet \neg S(x,n)$, by Discovery $\forall x \mathrel{|} B(x) \bullet x \knows[n] B(x)$ and by Exit $\forall x \mathrel{|} B(x) \bullet L(x,n)$. This answers part B.

The salient point is that each day, the fact at the end of the chain gets stronger, but the chain gets $1$ shorter.* Without $n \knows E(1)$ on the first day, the chain would be too short on the $n$th day and we'd have $0 \knows[n] E(n)$, which is just $E(n)$. So nobody would ever know $E(n)$, we would never be able to apply Non-discovery that final time, and the islanders would be stuck on the island forever - as they were before the Guru's announcement.

*If we used $\infty \knows E(1)$ instead of $n \knows E(1)$, then by Infinite Metadeduction each day we'd still have $\infty \knows[d] E(d)$. This makes the proof simpler, but hides the reason it doesn't work if $n \nknows E(1)$.