8

Here is a puzzle that is supposed to help illuminate common knowledge in game theory. Three girls are sitting in a circle, each wearing a red or white hat. Each can see the color of all hats except their own. Now suppose they are all wearing red hats.

It is said that if the teacher announces that at least one of the hats is red, and then sequentially asks each girl if she knows the color of her hat, the third girl questioned will know her hat is red. I understand the reasoning there. The first must have seen at least one red hat on the other two to say I don't know. And the second girl must have seen a red hat on the third, or else she would deduce that the first girl saw a red hat on her.

What I don't understand is the necessity of the teacher. Everyone knows there is at least one red hat. And, if we start with common knowlege, they should figure out that everyone else knows that. So is the teacher only introduced if common knowledge is not an assumption?

Source: http://cowles.econ.yale.edu/~gean/art/p0882.pdf

user178543
  • 183
  • 1
  • 4

2 Answers2

9

Without the teacher, everyone knows that there is at least a red hat, but nobody knows that everyone knows - the fact is not common knowledge.

With the introduction of the teacher,

  • Girl 1 doesn't answer. Due to common knowledge, 2 and 3 can reason: "1 knows there is at least one red hat, and since she doesn't know her hat color, 2 and/or 3 must have a red hat.

Without the introduction of the teacher,

  • Girl 1 doesn't answer. Without common knowledge, there is nothing 2 and 3 can reason on top of their prior knowledge: 2 will keep knowing that 3 has a red hat, and 3 will keep knowing that 2 has a red hat. Nothing more.

In other words: Without the teacher, the set of knowledge is:

  • 1: 2+3 have red hats
  • 2: 1+3 have red hats
  • 3: 1+2 have red hats

The teacher works as an injector of additional knowledge:

  • 1: 2+3 both know that there is at least one red hat
  • 2: 1+3 both know that there is at least one red hat
  • 3: 1+2 both know that there is at least one red hat

And, common knowledge means that in the next level, everyone knows that everyone knows

  • 1: 2+3 both know that I know that there is at least one red hat

etc, ad infinitum. This additional information is required to solve the puzzle.

FooBar
  • 10,712
  • 1
  • 29
  • 60
  • Thanks, but I'm still a little confused. Girl 1, observing two red hats (on 2 and 3), should then infer that 2 knows that 3 has a red hat and that 3 knows that 2 has a red hat. So every player realizes that the others see at least one red hat. Does that not mean everyone knows that everyone knows there is at least one red hat? Then, I don't understand why the teacher's statement constitutes additional knowledge. – user178543 Jan 29 '15 at 15:32
  • @user178543 because through the question the teachers asks, the girls can narrow down the possibilities of at least one red hat (so either 1,2 or 3 red hats) down to the correct answer of three hats. – user45891 Jan 29 '15 at 15:54
  • I understand now. This was very helfpul: http://people.duke.edu/~dgraham/handouts/HatsPuzzle.pdf. – user178543 Jan 29 '15 at 18:08
1

I think you essentially say: without the teacher's announcement, isn't it still common knowledge that everyone sees at least 1 red hat? (You said, "Everyone knows there is at least one red hat. And, if we start with common knowledge, they should figure out that everyone else knows that.")

I don't think it is. Person 1 sees Person 2 and 3 have red hats. Yes, 1 thinks: "2 sees a red hat on 3."

Yet, 1 further thinks: "If 2 sees my hat is white, then 2 thinks that 3 might see both white hats: mine and 2's, which might be white too. So I think that 2 might think that 3 might not see a red hat. In other words, I do not know that 2 knows that 3 knows there is at least 1 red hat. It is not common knowledge there is at least 1 red hat, because I think it's possible that 2 thinks that 3 does not see a red hat."

This breaks down the old solution in this way. Suppose 3 and 2 say sequentially that they don't know what color hat they wear. Then it's 1's turn. 1 thinks: "If 2 knows 3 sees a red hat, then my hat is red. Because otherwise my hat is white, so 2 concludes that his hat is the red hat that 3 sees. That's fine, but do I know that 2 knows that 3 sees a red hat? By the above, no, I don't know! I do not know that 2 knows that 3 knows there is a red hat. And in particular, it's not common knowledge!"

Conclusion: without the teacher's announcement, we lose (1) common knowledge and (2) the old solution in which the last person to guess can guess their hat color.

iko
  • 11
  • 2