4
$\begingroup$

Note: This is the second try at asking something that has not yet been answered by the excellent answers to the Oracle question or the skip-ahead question.

In this answer to my previous attempt at asking this question, there is an expansion of the tower of hypotheses that slowly collapses — one layer every night — in the accepted answer to the blue eyes riddle. It involves nested hypotheses like this one:

Hypo(99): Person(1) imagines that Person(2) imagines that … Person(99) imagines that Person(100) sees no people with blue eyes.

My question is: Since it is common knowledge (“everybody knows” ad infinitum) that all islanders observe the same situation on the island, why is Hypo(99) not immediately discarded as false?

Even in this nested hypothetical at the 100th level we can use the knowledge that everybody is on the same island, can we not? So seeing no people with blue eyes is purely hypothetical, we know that it cannot be true. If it cannot be true, then no new information is learnt during the first night.

This has been called a fascinating paradox within this riddle — please allow this question to focus only exactly on this paradox, and please don’t repeat the general reasoning for the inductive answer here!

$\endgroup$
1
  • 1
    $\begingroup$ My cousin's friend's uncle's coworker's son's girlfriend knows that her boyfriend's dad's coworker's nephew's friend's cousin knows that this is complicated. $\endgroup$ Jul 28, 2020 at 7:44

4 Answers 4

10
$\begingroup$

You don't know that everyone is in the exact same situation with respect to who has blue eyes. Everything else is the same, but the configuration of blue eyes is not known to be symmetric. (And in many tellings of the riddle, it's not.)

So, with 3 people, you can't say that "Person(1) knows that Person(2) knows that Person(3) sees someone with blue eyes": who would they see? It must be either P1 or P2. If you say it's P1, the issue is that P1 can't know that because they don't know their own eye color. If you say it's P2, the knowledge chain collapses at the P2 link. Each layer of nesting removes one potential blue-eyed person. Once you've made it through all the people, there is not necessarily a person with blue eyes anymore.

In more detail:

Let's look at the 3-person situation. P1 looks around, and thinks:

I know that P2 knows that there is at least one person with blue eyes. I also know that P3 knows that there is at least one person with blue eyes.

But I don't know that P2 knows that P3 knows that there is at least one person with blue eyes.

If my eyes are brown, then P2 can think "If my eyes are brown, then P3 might not see a brown-eyed person." So P2 might not know that P3 knows someone here has blue eyes.

And the 4-person situation:

P1: "Maybe I have brown eyes. If my eyes are brown, then P2 might be thinking:

P2: "Maybe I have brown eyes. If my eyes are brown, then P3 might be thinking:

P3: "Maybe I have brown eyes. If my eyes are brown, then P4 might be thinking:

P4: "Maybe I have brown eyes. Everyone else here has brown eyes. So I'm not sure that there is someone here with blue eyes."

So P4 doesn't know that someone here has blue eyes."

So P3 doesn't know that P4 knows that someone has blue eyes."

So P2 doesn't know that P3 knows that P4 knows that someone has blue eyes."that nobody here has blue eyes.

And finally, we outside observers look at this whole situation and conclude: "P1 doesn't know that P2 knows that P3 knows that P4 knows that someone has blue eyes."

Each layer of hypothetical removes a single person's eye color from the mix. Notice how in layer 4, all four people have had eyes that have been assumed to be potentially brown. Once you've gotten all 100 layers deep, every person in this hypothetical world has been given "maybe-brown" eyes by one assumption or another. Even though everyone knows that this hypothetical world isn't true, it's not common knowledge. Everyone knows that everyone knows that it's not true, but that chain of nesting doesn't run infinitely deep.

The reason you cannot discard Hypo(99) is because it is not a question of what P99 knows. Sure, P99 knows that someone else has blue eyes - you, as P1, can see that completely clearly! But you're not sure what other people know about this fact -- or more precisely, what other people know that other people know about this fact...

$\endgroup$
11
  • $\begingroup$ The last paragraph is the interesting one, and my question is still not answered: since everybody is on the same island, there is more knowledge than you consider! The hypotheticals you list are not the only source of information. If you want to argue that that is the case, then you need to supply proof of the absence of other sources of information. $\endgroup$ Jul 24, 2020 at 10:13
  • 1
    $\begingroup$ @AndrewSavinykh This is before the oracle. You're correct that the oracle makes this common knowledge. $\endgroup$
    – Deusovi
    Jul 24, 2020 at 14:21
  • 1
    $\begingroup$ @RolandKuhn It is not true that it is "commonly known". In the 3-person case, it is true that "everyone knows that everyone knows someone has blue eyes" -- but not everyone knows that fact. As P1, you do not know that P2 knows that P3 has blue eyes. As an outsider, you do, but that's because you can see P1's eye color. P1 can't. To P1, it is fully possible that P2 thinks P3 might see only brown. $\endgroup$
    – Deusovi
    Jul 24, 2020 at 15:22
  • 2
    $\begingroup$ @RolandKuhn "it is a directly observable fact, hence common knowledge". No, it is not. "Common knowledge" is not just "everyone knows that everyone knows this", but that knowledge continuing infinitely many times. In the 4-person situation, I know that B sees at least 2 people with blue eyes. But I don't know that B knows that C sees at least 2 people with blue eyes -- B might think C sees only one person with blue eyes (namely, D). It is not common knowledge: I do not know that other people know it. $\endgroup$
    – Deusovi
    Jul 24, 2020 at 17:05
  • 1
    $\begingroup$ @RolandKuhn Not sure which version of it you're talking about, but everyone knows the number of people on the island. Additionally, everyone knows that everyone knows that, and everyone knows that everyone knows that everyone knows that, and so on. This knowledge is not affected by nesting hypotheticals, because everyone knows their own on-the-island-ness status. When I think about what B knows, I don't remove him from it because he knows his own existence. $\endgroup$
    – Deusovi
    Jul 24, 2020 at 17:26
6
$\begingroup$

The answer by @Deusovi got the checkmark, also because @Deusovi helped me understand the broken link in my reasoning.

My mistake regarding common knowledge was the following: I was able to prove a statement (like “at least 98 people have blue eyes”) regardless of which hypothesis I make about my own eye color. From this independence of the result I concluded the generality of the proof of the statement, but that is the place where it goes wrong. Common knowledge can only be derived from facts that are symmetrically visible to all observers.

The deeper reason is that I used the hypotheses about my own eyes in the proof, and therefore the proof would be different for other people.

$\endgroup$
2
$\begingroup$

Consider the case where 4 people have blue eyes. Here, everyone knows that everyone knows that two people have blue eyes. What is unknown is if that fact is known by everyone.

P1 sees three people with blue eyes. P1 thinks, "If I have brown eyes, then P2, P3, and P4 know that at least two people have blue eyes but do not know that everyone knows that."

P1 might then think that P2 could think, "If I have brown eyes, then P3 and P4 know that someone has brown eyes but do not know that everyone knows that."

Because this is fundamentally a question about knowledge rather than eye colour, the next step is legitimate: P1 thinking that P2 might think that P3 could think that P4 might not see anyone with blue eyes. P1 knows that there is no way that P3 does think that P4 sees nobody with blue eyes - P3 knows that P4 sees P2. But P1 can't be sure that P2 doesn't think that.

With more people, it's similarly irrelevant how many people actually have blue eyes, as it's a matter of eliminating what other people might mistakenly believe.

What you seem to be hung up on is "nobody believes that only two or three people have blue eyes", which is correct. Nobody does. But each person believes that some other person might believe that a third person (and so on) could believe it. Once night 3 has passed, everyone knows that nobody could potentially believe that only three people have blue eyes.

You also seem to believe that there is common knowledge that can be removed from the equation - everyone knows that nobody leaves the first night. If this is the case, we could in theory skip the first night because no information is gained. Similarly, we could skip the second, third, etc. But how far can you go? If you see 99 blue eyes, can you skip 97 nights? But if you don't have blue eyes, then someone who does will skip 96 nights, so no conclusion is possible.

Put another way: the only communicable information is a single number. Suppose that the islanders could make a strategy in advance. They'd still have to wait the same number of days because the only information they can gain is, "there are not exactly n people with blue eyes."

$\endgroup$
7
  • $\begingroup$ «But P1 can't be sure that P2 doesn't think that» This is the crux of the matter, and I’d love to hear proof of this! My proposed counter-proof is that any person can see (not assume!) that every other person must see at least 2 pairs of blue eyes. So P1 knows that P2 knows that P3 knows that P4 knows that there are at least 2 pairs of blue eyes. Because that knowledge does not depend on the hypothesis about my own eye color. $\endgroup$ Jul 24, 2020 at 17:18
  • $\begingroup$ @RolandKuhn P1 doesn't know that P2 knows that P3 knows. If P1 did have brown eyes, then P2 would only see two people with blue eyes. Then when P2 considers having brown eyes, they would think that P3 would only see one person with blue eyes. So P1 knows that P2 knows, but does not know if P2 knows that P3 knows. $\endgroup$
    – Rob Watts
    Jul 24, 2020 at 17:26
  • $\begingroup$ But I can prove the statement “everybody sees 2 pairs of blue eyes” without having to rely on any hypothesis! This means that everybody else can perform the same proof. Which means that everybody knows to the Nth power, for any N. $\endgroup$ Jul 24, 2020 at 17:27
  • $\begingroup$ @RolandKuhn I can prove that statement. Everyone else can prove that statement. But in the 4p case, I do not know that everyone else can prove that everyone else can prove that statement. I know that everyone can prove everyone sees 2 pairs of blue eyes, but it's possible that not everyone else knows that too. If I have brown eyes, everyone sees 2 pairs of blue eyes, but one of my blue-eyed friends wouldn't know that another blue-eyed person sees 2 pairs of blue eyes. $\endgroup$
    – Deusovi
    Jul 24, 2020 at 17:30
  • $\begingroup$ @RolandKuhn I didn't make any assumptions about eye colors. If P1 does have brown eyes, then P1 knows that everyone can see two people with blue eyes, but P2 does not know that. P2 only knows that every can see at least one person with blue eyes. $\endgroup$
    – Rob Watts
    Jul 24, 2020 at 17:30
2
$\begingroup$

The reason this problem is difficult is because we're not just dealing with knowledge, we're dealing with knowledge about knowledge about knowledge, etc. Also, not only is everyone a perfect logician, it's common knowledge that everyone is a perfect logician. Let's look take a close look at what everyone knows to begin with for the different possibilities for three people - all with blue eyes (3B), two with blue eyes and one with green (2B), one with blue eyes and two with green (1B), and three with green eyes (0B).


In 3B each person with blue eyes knows that the two other people have blue eyes. They also know that those two people can see each others eyes, so those two people will know that at least one other person has blue eyes. (These people cannot tell if 3B or 2B is the truth)

In 2B, the person with green eyes knows that the two other people have blue eyes. They also know that those two people can see each others eyes, so those two people will know that at least one other person has blue eyes. (This person cannot tell if 2B or 3B is the truth)

In 2B, the people with blue eyes know that one other person has blue eyes. They also know that those two people can see each others eyes, so one of those two people will know that at least one other person has blue eyes, but the other might not. (These people cannot tell if 2B or 1B is the truth)

In 1B, the people with green eyes know that one other person has blue eyes. They also know that those two people can see each others eyes, so one of those two people will know that at least one other person has blue eyes, but the other might not. (These people cannot tell if 1B or 2B is the truth)

In 1B, the person with blue eyes knows that the two other people have green eyes. They also know that those two people can see each others eyes so neither one can see blue eyes that the person with blue eyes is aware of. (This person cannot tell if 1B or 0B is the truth)

In 0B, each person with green eyes knows that the two other people have green eyes. They also know that those two people can see each others eyes so neither one can see blue eyes that the first person is aware of. (These people cannot tell if 0B or 1B is the truth).


I tried to write these scenarios is a way that make the symmetry as obvious as possible - it's impossible for each person to tell if they are in the scenario where they have green eyes or blue. The only way that they can determine what color of eye they have is if someone else's behavior will be different based on what their eye color is. Now let's start adding information and see how it starts changing things:

The Oracle announces that someone has blue eyes.

Right away, the Oracle's behavior is different due to someone's eye color. If we were in 0B, then nobody would have blue eyes and the Oracle would not have announced being able to see someone with blue eyes.

If 1B were the case, then we know that there is one person who was unable to distinguish between 0B and 1B. Because the Oracle's behavior has eliminated 0B as a possibility, the one person with blue eyes knows immediately that they have blue eyes, so they will leave that night.

Nobody leaves the first night

If 1B had been the case, then someone would have left that first night. So now everyone knows that 1B is not a possibility. If 2B is the true situation, then two people will know that they have blue eyes, and will leave that night.

Nobody leaves the second night

If 2B had been the case, then two people would have left the second night. So now everyone knows that 2B is not a possibility. If 3B is the true situation, then three people will know that they have blue eyes, and will leave that night.


So why is this confusing?

The part that throws people off is "why does nothing happen for so long until everyone suddenly leaves?" It might help to run through a scenario where you pretend to be one of the people on the island. Remember, the only thing we have to go on is other peoples' behavior.

Consider this scenario - I just flipped a coin (yes, I actually grabbed a physical coin and flipped it) to decide if (heads) you have blue eyes or (tails) you have green eyes.

You see two people with blue eyes, so you know that you're either in 3B or 2B. You also know that if you're in 3B, the other two know they're in 3B or 2B. If you're in 2B, the other two only see one person with blue eyes and so know they're in 2B or 1B. You do not know which pair of scenarios the other two know themselves to possibly be in.

Take that a step further - if they're in 3B or 2B, their logic will match yours and they'll believe each person to possibly be in 3B, 2B, or 1B. If they're in 2B or 1B, though, they'll believe the others to be in 2B, 1B, or 0B.

This is where the Oracle's announcement comes into play. You don't know what the others believe, and you don't know if you have blue eyes or green eyes, but because the Oracle has seen someone with blue eyes you now know for a certainty that nobody believes 0B to be the case, or believes that someone else believes it to be the case (or in the case of more people, believes that someone else believes that someone else believes that...).

From here on out, the possibilities start to collapse. You still know you're in 3B or 2B. If you're in 3B, the other two also know they're in 3B or 2B. If you're in 2B, then the others believe they're in either 2B or 1B. However, if the other two believe they might be in 1B, they would also believe that the other of them could have believed they were in 1B or 0B and now know that they are in 1B and they are the one person with blue eyes.

The first night you're not surprised when nobody goes home - after all, you know that both the other two people have blue eyes, so each can see someone else with blue eyes. However, you don't know if the other two were surprised by that. Let's consider again the possibilities:

You're in 3B or 2B. If you're in 3B, the other two also know they're in 3B or 2B. If you're in 2B, the other two believe they're in 2B or 1B. That would mean that they were surprised when nobody went home last night and they now know that they're in 2B. So now they either know they're in 2B, or know they're either in 2B or 3B.

Now the second night comes and...

The other two go home. You're surprised because you did not have the same information that they did - your eyes are not blue. If you had been in 3B, they would have also thought they were in 3B or 2B and, not knowing, they would not have left. But because you were in 2B, they had known that they were in 2B or 1B. So when the Oracle made the announcement and they each realized that they could not be in 0B, they knew that the other one might know for sure. After the first night when nobody left, they knew for sure that both of them had blue eyes.

I did in fact flip a coin, but then disregarded the heads I'd flipped because I realized that everyone else has been considering scenarios in which everyone's eyes are blue. I hope that this did in fact surprise you that it turned out to be a different scenario. Also, I'm intentionally being verbose here just to hide the fact that it ends on the second night instead of the third. If it had gone another night I would have ended up explaining the current situation in a little more depth and explained how you now knew that you also had blue eyes. Hence my attempt to make the spoiler blocks as big as they would have been.

Another way to look at it

Consider the scenario in which some number of people have blue eyes, some number have green eyes, and you don't know which group you belong to. Because you know everyone here is a perfect logician, you know that the people with green eyes will never come to the conclusion that they have blue eyes. So in a sense, they don't matter. So you have a group of people with blue eyes, and have two scenarios to consider - one in which you also have blue eyes and you belong to the group, and one in which you don't have blue eyes. In the latter scenario you don't actually matter - you'll never come to the false conclusion that you have blue eyes, and so it's just the people who do have blue eyes who matter for the problem.

As to why the nested hypotheticals need to be considered, they're another way of representing what I was talking about with possibilities. Up until the Oracle made the announcement, you already knew that someone had blue eyes, and already knew that everyone else knew that someone had blue eyes, but now you know that everyone knows that everyone knows at least one person has blue eyes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.