Monday, September 20, 2010

The Story of the Blue Eyed Islanders

One of the most perplexing problems I have ever encountered is the infamous “Blue Eyed Islanders” puzzle. The perplexing aspect is a seeming paradox I will get to shortly, but the nominal solution involves straightforward induction, and is relatively easy to understand. It is possible that the story also has some applicability to more realistic human societeies.

The puzzle may be stated as follows:

There is a village where everyone has either blue eyes or brown eyes. Each person can see what eye color everyone else has, but each does not know the color of his or her own eyes. It is strictly forbidden for any islander to tell anyone else what color he/she has. If on a given day one happens to find out the color of ones own eyes, one must hurl oneself into the volcano at dawn the next day.One day an outsider comes to visit, a person who is known to always tell the truth. This person asserts for all to hear that “some of the people in this village have blue eyes”. Within a certain number of days, all in the village have killed themselves.The relatively easy parts of the puzzle are "why", and "when" does this happen?

Assume first that there is only one blue eyed person. He does not know that he has blue eyes until the fateful day of the outsider’s statement, but he does know that all of his fellow islanders have brown eyes. He thinks it is possible that he has brown eyes himself. But after the statement that there is at least one blue eyed person, he knows that it must be he himself, and the next day he commits “volcanacide”. If he were to see any other blue-eyed persons, he would not do himself in on the first dawn. So when the remaining brown eyed people see him do the deed, they all know that he saw all brown eyes, and thus they all have brown eyes. On the second dawn, they too jump into the fiery pit.

It is easy to see that if there were two blue-eyed persons, say Sam and Sara, each would think it possible that the other blue eyed person is the only one. But Sam sees that when Sara does not jump into the volcano upon the first dawn, he knows that he also has blue eyes, and on the second dawn Sam jumps in, and so does Sara, for exactly the same reasoning with regard to Sam. All the rest would jump in the third day, since they then deduce that they all have brown eyes, since evidently only Sam and Sara had the blue eyes the outsider noticed.

From induction, it follows that for a village population of N people, with X blue-eyed people and N-X brown eyed people, all of the blue eyed people will hurl themselves into the volcano X days after the outsider’s assertion. On day X+1, the brown eyed people will follow.The paradox is that every individual person in the village already knew, before the outsider’s visit, that there were some people in the village that have blue eyes (assuming that there was more than 1). They simply could see them, because if you were a blue, you’d see X-1 blues, if you were a brown, you’d see X blues. So what did the outsider tell them that they did not already know? That is, what specific new information did the outsider give them that led to the mass suicide of the village?

To illustrate this more concretely: What if there were 1000 villagers, 400 (say) with blue eyes. Before the outsiders visit and his unfortunate faux pas, each native knew that there were at least 399 blue eyed people on the island. Doesn’t it seem absurd that the statement that there is at least one would cause all 400 of the blue eyed people to hurl themselves to their doom on the 400th dawn, and the rest of the browns would follow on the 401st dawn? Thus, in this example, it would take over a year for the village society to cease to exist.

It seems that if one accepts logical induction, as surely one must, this surprising outcome must occur. The situation was stable before the outsiders made his observation, but the observation rendered that society unstable, and it rather quickly became extinct. It makes one wonder about possible applicability to more realistic human societies: could it be that some of the seemingly arbitrary taboos that have been put in place in various closed civilizations could somehow serve to stabilize them? In the example above, the particular taboo seems silly and unrealistic (and have they no mirrors or reflecting surfaces?). And even if an arbitrary taboo does bring about stability, we must also ask whether it involves a morally acceptable restriction, and if it is the only way that such stability could be achieved.

Perhaps the morale to this story is that there should be no taboos, but rather that human societies should be based on universal morality, that in turn is based on game theoretic reasoning such as is involved in the “prisoners dilemma” (this is really a sort of a generalized “golden rule”, wherein each person respects the rights of others to “live and let live”). But that is another tale, hopefully to come in a later blog.


32oH2O said...

The two envelope problem. One envelope has twice the other. You are given an envelope, see that it has $2, and asked if you want to switch.

Paradox: Open the first envelope and find $2. To switch, you are risking $1 to gain an additional $2. Intuition says switching can’t matter, but the EV of switching seems to be positive. Clearly, the intuition does not match the math, why?

Let’s set the problem up in a general sense. The lesser amount of money in an envelope is defined by a function l(x). The x is a randomizing variable; you could look at it as being the ordinal integer indicating the first lesser amount that is randomized. The big amount of money in an envelope is defined by the function B(x) which is equal to 2l(x). Now when we look at switching, if we started with l(x), we can gain l(x). If we started with B(x) we can lose l(x). The EV overall is 3l(x)/2. And the EV of switching is zero.

So, given that the problem is solved, why do we initially calculate a faulty EV? In our first look, we essentially said that either:
l(x) = 2; therefore, switching gains 2
B(x) = 2; therefore, switching loses 1
However, these statements are wrong since the functions should be evaluated at different places along x…we know that when evaluated at the same x, B will be twice l, and will occur with the same probability. Since the envelopes come in pairs, it is faulty to try to evaluate l(pi) along with B(e). It is an apples to oranges comparison where we tend to look at it as equal probabilities cancelling out, when the real problem has no such constraint.

The above solution does not constrain the probability functions for l and B, does not limit values for l or B, and does not limit the number of distinct allowable values for l and B.

32oH2O said...

The blue-eyed islanders...unfortunately your game ends with a loss if you determine your eye color. It doesn't change the puzzle, but only makes it easier to think about and to play if you are whisked off to Nirvana with a hotty on each arm when the game ends. I doubt the puzzlemakers had that literary solution in mind.

By the way, I developed this solution thinking about the five day hanging paradox, which I think is "solved" with a concrete definition of win/loss conditions.