The reason for the traveler in the blue eyes/ brown eyes problem

[borisp]

Recently I posted the "traveler problem," which was also stated here a few months ago with different but equivalent vocabulary. The real question amounts to "why the traveler (stranger)?"

link to original

The answer given in the above thread was not quite correctly justified, although it contains the essence of the idea. Basically the proof of the statement "everyone dies (leaves)" is by induction, and saying that the traveler is necessary to start the induction is essentially saying that any proof that the traveler is unnecessary probably wouldn't use induction.

So, why the traveler? In other words, what is precisely the new knowledge that the islanders (villagers) have?

(Some clarifications: "Rational agents" are defined to have certain knowledge and are not allowed to act on anything but knowledge that follows from their original knowledge. In this problem, the islanders know that there are two types of eye color (i.e. horns or no horns), and they know the customs, and they know that everyone else is also a rational agent with exactly this knowledge.)

Hint in white:

<font color="white">Consider what the islanders know about the other islanders' knowledge. How does this change when the traveler makes the announcement? </font>

[soon2bepro]

First I would like to comment that in this particular example not everyone leaves, just the ones with horns (doesn't make much difference but still)

It seems that the stranger provides additional information by letting the last horned guy in the chain of assumptions know that he has horns, but I can't quite pin down how exactly it is that this is new information.

I've spent roughly 7 hours thinking about this subject just in the last couple of days, and probably some more back in that original thread 8 months ago; and still can't quite get a "feeling" of understanding for the solution.

[PairTheBoard]

[ QUOTE ]
First I would like to comment that in this particular example not everyone leaves, just the ones with horns (doesn't make much difference but still)

It seems that the stranger provides additional information by letting the last horned guy in the chain of assumptions know that he has horns, but I can't quite pin down how exactly it is that this is new information.

I've spent roughly 7 hours thinking about this subject just in the last couple of days, and probably some more back in that original thread 8 months ago; and still can't quite get a "feeling" of understanding for the solution.

[/ QUOTE ]


Suppose there are 3 blue eyed monks. All 3 can see that there are 2 other monks with blue eyes. Everybody else can see there are 3 blue eyed monks. But what nobody knows is whether they themselves have blue eyes. Now a traveler comes and "Informs" them that there is at least 1 blue eyed Monk in their midst. But they all knew this already didn't they? Here's the thing. Yes, they all knew that Information. But what they DIDN'T KNOW was whether everybody else knew that everyone else knew that information.

That's what the Traveler now guarantees.

btw, Their reasoning is not really by "Induction". The proof by Induction shows that in any similiar situation where there are any number of blue eyed monks, the reasoning exists that produces the same conclusion for the number of days required with respect to the number of blue eyed monks. But for a specific case like 3 blue eyed monks, or 100 blue eyed monks, induction is not required. It is a straightforward chain of deductions on what the 100th monk thinks the 99 monks think the possible 98 monks think the possible 97 monks think the possible ... 1 monk thinks.


PairTheBoard

[borisp]

Right, the proof of the statement "everyone dies no matter what" is by induction, but in any real application, the islanders/villagers perform a finite chain of reasoning.

A good illustration is to imagine that the inhabitants had received this announcement in the mail, and that no one ever talks about the mail. In that situation, everyone goes along happily as if nothing ever happened (except in the specific case where one person has blue eyes), because no one knows what everyone else has gotten in the mail.

Specifically, if there are N people with blue eyes on the island, the phrase "Everyone knows that everyone knows that everyone knows that ... (N times) ...someone has blue eyes" changes from false to true. In other words, the knowledge that "someone has blue eyes" changes from private to public.

I think this is neat because it illustrates that just because something is on everyone's mind does not mean that they do anything about it, or that they can draw conclusions from it. The public announcement is something tangible and it has consequences, even in the event that it announces nothing new. I see this as analogous to when a poker book is written, in that everyone can have a common strategy, but once it is printed in a book, the strategy inevitably evolves, although it seems as if nothing new has been introduced.

[LeadbellyDan]

[ QUOTE ]
[ QUOTE ]

Suppose there are 3 blue eyed monks. All 3 can see that there are 2 other monks with blue eyes. Everybody else can see there are 3 blue eyed monks. But what nobody knows is whether they themselves have blue eyes. Now a traveler comes and "Informs" them that there is at least 1 blue eyed Monk in their midst. But they all knew this already didn't they? Here's the thing. Yes, they all knew that Information. But what they DIDN'T KNOW was whether everybody else knew that everyone else knew that information.

That's what the Traveler now guarantees.



[/ QUOTE ]

I guess the basis for why this works must be something like this but what you say doesnt explain why this works no matter how many have blue eyes.

If there were, say, 50 blue eyed horned monks (you started the exampled mixing so I thought I'd go all the way) within the group then the blue eyed horned monks would all know that everybody else knows that there are at least 48 blue eyed horned monks.

[ QUOTE ]

It is a straightforward chain of deductions on what the 100th monk thinks the 99 monks think the possible 98 monks think the possible 97 monks think the possible ... 1 monk thinks.

[/ QUOTE ]

I think what this stems from is that there is no monk which everyone knows has blue eyes. The knowledge of the group as a whole - what everyone agrees upon - does not include "Billy has blue eyes," "Tom has blue eyes," "Sally has blue eyes," etc and so it also cannot include "there is at least one blue eyes (possibly horned) monk."

*Im nearly starting to understand this but I'm too tired and can't think any more. I'll just post this for now - sorry if its incoherent. I find this fascinating btw - I'm suprised its not more well known.*

[borisp]

[ QUOTE ]
I'm suprised its not more well known.

[/ QUOTE ]
It is a very well known and well understood problem, in the academic sense. I wish it were more commonly well known.

One key to understanding this problem lies within the definition of rational agent: we stipulate their universe of knowledge. So for a rational agent to take an action, it must either follow from their original knowledge, or from new knowledge, otherwise they are left to do nothing.

Knowledge such as "Tom has blue eyes" is private to these agents. Sam knows it, but he knows that Tom does not. Any islander that sees N people with blue eyes knows that "everyone knows that everyone knows that everyone knows that ...(N-1 times)...someone has blue eyes." He knows that all other islanders know this is true with at least N-2 instances of "everyone knows." When the traveler arrives, each islander now LEARNS that this statement is true for arbitrary N, and they each also understand that all others know this. This new knowledge is precisely the cause for action on the part of the rational agents.

Btw, this is exactly what PairTheBoard was saying, I'm just offering a different (more elaborate) way to say it. Personally, I believe this example has philosophical implications regarding the power of "publication." I see it as negating criticism of publications that only outline what everyone already knows. For example (I mentioned poker books in the other post), many studies that discuss the various effects of recreational drugs in a scientific manner are often criticized for stating nothing more than what is obvious, but their publication is a necessity if we want any significant reform to take place.

Edit: So I guess "more elaborate" should now be replaced by "equally elaborate." [img]/images/graemlins/smile.gif[/img]

[PairTheBoard]

[ QUOTE ]
If there were, say, 50 blue eyed horned monks (you started the exampled mixing so I thought I'd go all the way) within the group then the blue eyed horned monks would all know that everybody else knows that there are at least 48 blue eyed horned monks.



[/ QUOTE ]

The 50 with Blue Eyes would wonder, "Do I have blue eyes?". Then they think, "If I don't have Blue Eyes what do the 49 Blue Eyed monks I see think?". Then, "If I don't have Blue Eyes, the 49 will wonder if they have Blue Eyes and think just like I'm thinking. They'll think, "If I don't have Blue Eyes what are the 48 thinking? Well they will have to think like I'm thinking and wonder if they have blue eyes and think If they don't have blue eyes, what are the 47 thinking? They will think, If I don't have blue eyes what are the 46 thinking? ...". Finally, the chain gets down to the conjectured 2 monks thinking, If I don't have Blue Eyes why doesn't the other guy know he must have blue eyes Now that the Traveller has pointed it out to him?"

It's a chain of conjectured monks making conjectures about other monks. It's the conjectured lone monk that needs the traveller's information. It doesn't matter what every monk can see. It's what every monk thinks every monk thinks every monk thinks every monk thinks every monk thinks .... the lone conjectured monk would think now that the traveller has made the announcement.

PairTheBoard

[Max Raker]

The only case where you need a visitor is when their is exactly one guy with a horn right? If there is more than one person with a horn his statement does not give new information to ANY person so it would play out the same way. (If the number of days passed is greater than the horns you count you gotta go) Am i missing something?

[borisp]

[ QUOTE ]
The only case where you need a visitor is when their is exactly one guy with a horn right? If there is more than one person with a horn his statement does not give new information to ANY person so it would play out the same way. (If the number of days passed is greater than the horns you count you gotta go) Am i missing something?

[/ QUOTE ]
Consider the case with two blue eyed islanders. All of the islanders know that someone has blue eyes. But the two islanders that have blue eyes don't know that the other blue eyed inhabitant knows that someone has blue eyes. After the traveler comes, they now know this.

It is helpful to compare the traveler's announcement with the same announcement received in the mail. This illuminates the difference between "public" and "private" knowledge. The traveler makes the knowledge that "someone has blue eyes" public.

[Max Raker]

[ QUOTE ]
[ QUOTE ]
The only case where you need a visitor is when their is exactly one guy with a horn right? If there is more than one person with a horn his statement does not give new information to ANY person so it would play out the same way. (If the number of days passed is greater than the horns you count you gotta go) Am i missing something?

[/ QUOTE ]
Consider the case with two blue eyed islanders. All of the islanders know that someone has blue eyes. But the two islanders that have blue eyes don't know that the other blue eyed inhabitant knows that someone has blue eyes. After the traveler comes, they now know this.


[/ QUOTE ]

But now if the number of blue eyes is greater than 2 everyobdy knows that everybody knows that some people have blue eyes. So I don't see a need for the traveler.