Of course, here we are talking about an abstraction, for is anything ever truly common knowledge?
Even if we’re sitting beside each other watching tel- evision, and a weather bulletin flashes along the bottom of the screen, am I sure that you saw it? Probably. But can I be sure that you saw me watching the bulletin? Possibly. But can I be sure that you saw me watching you watching the bulletin? Perhaps not. Although, in reality, knowledge may not hold for the entire infinite levels of beliefs required to satisfy common knowledge, it may not be a bad approximation for a lot of settings, in the sense that people act “as if” something is common knowledge.
Before we move on, let me describe an intriguing puzzle that conveys the power of common knowledge. A group of recently deceased individuals stand before the pearly gates to heaven. St. Peter is waiting for them there. (Bear with me if you don’t buy into the whole St. Peter shtick.) He tells them that only saints may enter right away, and a saint is demarcated with a halo over the head. Those who are not saints, but who try to enter, will be banished to hell. Those who are not saints and do not try to enter will go to purgatory for a while and then enter heaven. There is one problem in determining whether you are a saint: No one sees whether there is a halo over his or her own head, though each sees the halos over the heads of others. St. Peter provides one last piece of information: he announces that there is at least one saint in the group.
St. Peter begins by inviting anyone to walk through the gates. If no one does, he then asks again, and so forth. Will the saints be able to figure out who they are? They can if it is common knowledge that there is at least one saint among them.
To see how the argument operates, suppose that there is, in fact, exactly one saint. This is not initially known; everyone knows only that there is at least one saint. The person who is that singular saint will look around and see no halos over the heads of the others. Since he knows that there is at least one saint, he concludes that he must have a halo over his head. He then enters heaven. Admittedly, that was easy and, in fact, didn’t require common knowledge, but only knowing that there is at least one saint.
Now suppose there are instead two saints in the group, and let’s name them Tyrone and Rita. During the first calling by St. Peter, each person looks around and sees at least one person with a halo. (Those who are not saints will see two people with halos.) No one can conclude that he (or she) is a saint, so no one walks through the gates. Let us remember that each person knows that the others know that there is at least one saint. That no one walked through the gates must mean that each person must have seen at least one other person with a halo, for if the person hadn’t, then she could infer that she is a saint.
2.9 A Few More Issues in Modeling Games 45
Since everyone, including a person with a halo, saw at least one person with a halo, there must be at least two saints. Since Tyrone sees exactly one other person with a halo (Rita), and he knows that there are at least two saints, Tyrone concludes he, too, must have a halo. By an analogous logic, Rita draws the conclusion that she has a halo. They both walk through the gates on the second calling.
Okay, we could solve the problem when there are two saints. But can we do it when there are three saints? Most definitely, and what allows us to do so is that each person knows that there is at least one saint, each person knows that everyone else knows that there is at least one saint, and each person knows that everyone else knows that everyone else knows that there is at least one saint. Do you dare follow me down this daunting path of logic?
Suppose the group has three saints, and their names are Joan, Miguel, and Tamyra. As in the case when there are two saints, no one can initially conclude that he or she is a saint. Because each person sees at least two halos (Joan, Miguel, and Tamyra each see two, and everyone else sees three), knowing that there is at least one saint doesn’t tell you whether you have a halo. So no one enters during the first calling. Since no one entered then, as we argued before, everyone infers that everyone must have seen a halo, which means that there must be at least two saints. So what happens in the second calling? Since there are in fact three saints, everyone sees at least two halos during the second call- ing, in which case no one can yet conclude that he or she is a saint. Now, what can people infer from the absence of anyone entering heaven during the sec- ond calling? Everyone concludes that everyone, including those folks who have halos, must have seen at least two halos. Hence, there must be at least three saints. Since Joan sees only two halos—those above the heads of Miguel and Tamyra—Joan must have a halo. Thus, she walks through the gates on the third calling, as do Miguel and Tamyra, who deploy the same logic. The three saints figure out who they are by the third calling.
Suppose there are n saints? The same argument works to show that no one enters until the nth calling by St. Peter, at which time all n saints learn who they are and enter. To derive that conclusion, it takes n levels of knowledge: everyone knows that there is at least one saint, everyone knows that everyone knows that there is at least one saint, everyone knows that everyone knows that everyone knows that there is at least one saint, and so on, until the nth level. Hence, if it is common knowledge that there is at least one saint, then the saints can always eventually figure out who they are.
It is said that, in order to succeed, it’s not what you know, but whom you know. However, game theorists would say that it’s not what you know, but what you know about what others know, and what you know about what oth- ers know about what you know, and. . . .