Puzzling Asked on June 15, 2021
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!
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...
Correct answer by Deusovi on June 15, 2021
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."
Answered by Spitemaster on June 15, 2021
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.
Answered by Roland Kuhn on June 15, 2021
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...
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.
Answered by Rob Watts on June 15, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP