Insights by Danielle Fong

Terry Tao’s recent post on a classic logical puzzle has seeded a bloom of activity in the nerdsphere. A friend of mine introduced it to me over mugs of steamed milk in the graduate college coffee house; I was telling him of recent work I’d been doing on the soundness of emergence of Nash equilibria, and where sufficient conditions arise in real life.1 It was an enjoyable conversation, though I wasn’t afforded the luxury of working it out for myself. If you’d like to struggle through the problem on your own, read Terry’s post, and only return after the break when you think you’ve solved it. (why am I writing this? It started as a comment on news.ycombinator.com, and I couldn’t help myself)

This problem is subtle, and wording is important, so I’ve reproduced the statement from Terry’s blog (emphasis mine) [editor’s note: Terry didn’t intend for a particular subtlety, and so has reworded his main post. He says that it had an ‘unexpectedly interesting subtlety in its formulation, but was not the puzzle I had actually intended to write’. He’s posted the original here]:

There is an island upon which a tribe resides. The tribe consists of 1000 people, 100 of which are blue-eyed and 900 of which are brown-eyed. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and highly devout, and they all know that each other is also highly logical and highly devout.

One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe.

One evening, he addresses the entire tribe to thank them for their hospitality.

However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, remarking “how unusual it is to see another blue-eyed person like myself in this region of the world”.

What effect, if anything, does this faux pas have on the tribe?

I’ve italicized the statement hosting the subtlety. It is known to everyone that if any tribemember discovered his or her eye color, they would dutifully commit suicide at noon the following day. And yet. The statement cleverly leaves open whether every person knows that every other person is as logical, or as devout, or as committed to the duties of ritual sacrifice, as they are.

To jump the gun, the statement doesn’t explicitly state the logical nature and devoutness of all tribespeople as common knowledge.

Hopefully examples will deliver me from vagueness. Consider tribes with one, two, and three blue eyed people on islands Galileo, Hippasus, and Russell. 2,3,4

On Galileo, after the gaff, the sole blue eyed unfortunate notices that none of his people share his tint of iris, and reconciles himself to a midday doom.

On Hippasus, one day later, our fated blue-eyed duo, fully aware that the other would have extinguished were he or she the only blue eyed resident, are forced to draw the conclusion that they are blue eyed, and so they disappear.

But on Russell, confusion sets in. Three blue eyes islanders know the two others. They know that each would commit suicide if they discovered their eyecolor, and they know that on the previous two days, no such thing happened. It would seem that the group would meet a bitter end. As the reasoning usually goes, each of the three, knowing the other two, would infer that the others continued survival could only mean the existence of other blue eyes on the island — theirs!

But wait. Let’s examine this more closely: take the blue eyed islanders, let’s call them, err, Alice, Bert, and Cecil. Alice sees Cecil and Bert; she knows that they as well as the rest of the tribe, and knows they’d indeed follow protocol if either discovered their eye color. What she doesn’t know for certain is whether Bert knows that Cecil would kill himself over eye pigment (even though he in fact would). Therefore, she doesn’t know for certain that a tribe with two blue eyed members would homogenize itself on the second day, she only knows that this would be true were she one of the members. She therefore cannot deduce that she has blue eyes, and the tribe’s taboo keeps information from spreading any further. Our trio is saved. 5

What would happen if all islanders knew that all islanders followed the same rules (as is explained in the variant posted by xkcd)? Instead of confusion, Alice would be certain that Bert and Cecil wouldn’t have survived were they the only blue eyed people, and so she must be the last. They all would die on the third day. Indeed, any group of blue-eyed 6 islanders under the same conditions would all meet their fate the same way.

There are other variants, Anatoly brings up a very interesting metaproblem where proactive tribe’s members might decide to save the others through early self-sacrifice. The analysis of this, and other metaproblems, goes very deep. It will have to be the subject of another post.

In any case, I hope I’ve thoroughly explored the magic. Or at least spoiled it!

As Terry writes,

“The remarkable thing about the puzzle, to me, is how such a subtle and seemingly academic change in the knowledge environment eventually propagates to have a concrete and dramatic effect.”

Notes:

I’ve been meaning to write that article for ages, in fact I was urged to do so by my friends in politics, since models from game theory such as the Centipede Game, the Prisoner’s Dilemma, and Mutually Assured Destruction remain dominant teaching devices, and Nash equilibrium strategies continue to be prescribed and accepted as applicable by acolyte bureaucrats. Yet I’m writing this article, and not that one. The power of social news compels me.

Galileo was famously persecuted by the Church due to his advocacy of essentially logical methods and conclusions. (though you probably already know that)

The philosopher Hippasus was said to have been either expelled from the Pythagorians or drowned at sea for his proof that the square root of two was irrational.

While Bertrand Russell’s magnum opus, the Principia Mathematica, was doomed at inception due to the underexamined implications of self reference, in this case, letting meta-knowledge probe only so deep means our Russellian islanders are saved.

I’m aware that some may object: ‘but doesn’t “and they all know that each other is also highly logical and highly devout” imply common knowledge?’ I concede that this might be an interpretation in some English. Not mine; what kind of language distinguishes knowledge from meta-knowledge but not meta-knowledge from meta-meta-knowledge? Sounds illogical. Oh wait.

A common misconception is that the brown eyed people would die too. But that’s not quite right since none of them are sure that their eyes aren’t actually green, grey, or magenta.