There are some things everyone knows: bears defecate in woods, the pope isn't Protestant, and land wars shouldn't be started in Asia. Everyone knows them, so these things are common knowledge, right? Not necessarily. To see the difference, consider the dread tale of the Prisoners of Carpathia.
The Dungeons of Carpathia are a miserable place. Each dungeon cell contains five prisoners, chained to the wall by their ankles, and gagged so that they cannot speak. The prisoners are kept in darkness all day and all night, except for a brief moment in the morning, when the guards come to feed them. Once imprisoned, prisoners can expect to remain in the dungeon for the rest of their lives.
But the dungeon guards like to offer them hope. On their first night, while the prisoners are sleeping, the guards secretly mark the foreheads of some prisoners with a blue symbol -- the symbol of freedom. The next morning, the guards tell them that any prisoner who is certain that his forehead is marked with the blue symbol can go free. They then ask the prisoners to raise their hands if they are certain their foreheads are marked. And every morning the guards return to ask the same question.
The prisoners cannot see the symbols on their own foreheads, but can immediately see which of their cellmates are marked. Therefore, if it is common knowledge that at least one prisoner is marked with the symbol, then the marked prisoners will be able to free themselves. To see this, consider the case where only one prisoner is marked. On the first morning, this prisoner will see that none of his cellmates is marked, and, since it is common knowledge that at least one is marked, he will be able to deduce that he himself must be marked. Or consider the case where two prisoners are marked. On the first morning, a marked prisoner, A, will see that only one of the other prisoners, B, is marked. (Prisoners in Carpathia are known only by their letter codes.) But when the guards ask their question, A will see that B does not raise his hand. A will then deduce that it cannot be the case that he is unmarked -- since then B would have seen four unmarked cellmates, and realised that he was the only one marked. B will employ similar reasoning. (Prisoners in Carpathia are very logical -- they need to be.) And so when the guards ask their question on the next morning, A and B are both certain that they are marked, and raise their hands. The same reasoning can be employed for higher numbers of marked prisoners. In general, if n prisoners are marked, the marked prisoners will know they are marked after n mornings -- if it is common knowledge that at least one prisoner is marked.
When is it common knowledge that at least one prisoner is marked? When two prisoners are marked, the unmarked prisoners each see two marked cellmates, and the marked prisoners each see one marked cellmate. So then everyone knows that at least one prisoner is marked. Is this enough for the marked prisoners to free themselves? Let us see. On the first morning, prisoner A will see that prisoner B is marked, and vice versa. On that morning, when the guards ask their question, neither A nor B raises his hand, as before. But this time, prisoner A cannot be sure why prisoner B didn't raise his hand. For while A knows that at least one prisoner is marked -- after all, he can see the marking on B -- he doesn't know that B knows that at least one prisoner is marked. For all A knows, B might see four unmarked cellmates and just assume everyone is unmarked, including him. So it's not sufficient for everyone to know that at least one is marked -- in this case, everyone must know that everyone knows that at least one is marked.
But even that is not enough in general. When three prisoners are marked, everyone knows that at least one is marked, and everyone knows that everyone knows that at least one is marked. (Each marked prisoner sees two other marked prisoners, and knows that each marked prisoner he sees can see the other one.) But the marked prisoners still cannot free themselves. On the first morning, A knows that B knows that C is marked, but does not know if B knows that C knows that B is marked. As far as A is concerned, A might be unmarked himself, and B might see A unmarked and also think himself unmarked. And so A thinks that B might think that C sees four unmarked cellmates; A thinks that B might think that C thinks that no one is marked. Therefore A can never be sure why B and C don't raise their hands on the first two mornings, and can never raise his hand himself.
In fact, even if all the prisoners are marked, it can be shown that the prisoners can never know enough to free themselves. If n prisoners are marked, then for the marked prisoners to have a chance of freedom, everyone must know that everyone knows that... everyone knows that at least one prisoner is marked, to a depth of at least n levels. But since the prisoners have no way of communicating with each other, the only way they can have a chance of knowing this is if the guards explicitly tell them that at least one prisoner is marked. And the guards never tell them any such thing. Very cruel people, the dungeon guards of Carpathia.
Hopefully this little tale has illustrated the difference between something everyone knows and something that is common knowledge. But the tale still doesn't tell us what common knowledge actually is. The usual definition of common knowledge is recursive: x is common knowledge among a certain group if everyone in the group knows x, and everyone in the group knows that x is common knowledge in the group. Therefore, in a group of n people, it is not sufficient for "everyone knows" to go n layers deep: in fact, it must go infinitely deep.
A typical example is the following. As part of their job, Xavier and Yves must lift and carry a large vat of battery acid. If either of them lifts his end first, the vat tips over and spills highly corrosive battery acid over the other. Therefore, they must both begin lifting at the same time: Xavier should not lift his side unless he knows Yves will lift his side at the same time. But what if Yves doesn't know that Xavier knows that Yves will lift his side at the same time? Yves will hardly lift his side unless he does, so Xavier should not lift unless he knows that Yves knows that Xavier knows that Yves will lift his side at the same time. And so on. In fact, if Yves and Xavier were truly logical about it, they would both stand there reasoning about each other's knowledge indefinitely, leaving the vat to be carried by their more reckless colleagues.
Of course, in a real rational agent system, agents don't reason towards common knowledge in this way; instead some pieces of knowledge are made common (perhaps through being put on some sort of record accessible to all agents, like a conversational record) and then from the fact that some x is common knowledge, it can be deduced that all the agents know that they all know that they all know it, to some arbitrary depth. Such infinitely deep common knowledge operators can be found in almost any multi-agent logic. They come at a heavy computational cost, but they are considered so essential to model any realistic multi-agent system that most logic designers would rather keep them and sacrifice expressivity elsewhere.
I can see their point. Infinitely deep common knowledge is a nice mathematical concept, and people have shown its various nice mathematical properties, and it works. But in a practical sense I think the notion that common knowledge goes infinitely deep is nonsense. People don't reason about other's knowledge to any great depth. I start to struggle after about three levels deep -- I can think about what other people know, and what other people think I know, but beyond that it's quite a bit of effort. Various psychological studies have shown that I'm not alone. A recent study placed pairs of volunteers against in other in a special game in which there were strategic advantages to reasoning about each other's beliefs to a depth of three. But none of the subjects ever actually reasoned to a depth of three -- in fact, only the cleverest players went even to a depth of two.
For this reason, I got a bit dizzy writing about the Prisoners of Carpathia, and perhaps you got a bit dizzy reading it. Even in that example it is sufficient for knowledge to go only n levels deep for n prisoners -- and that example is highly contrived. If there were twenty prisoners in a cell, and all twenty were marked, I think they'd have a hard time reasoning their way to escape even if it were common knowledge that at least one was marked.
People make cooperative decisions all the time without reasoning about each other's knowledge to any significant depth. Consider the case of six pallbearers carrying a coffin. If one of them lifts his end too soon, the coffin tips over and spills the last mortal remains of great uncle Hubert all over the pavement. But does grand nephew Humbert really think about what cousin Albert thinks about what uncle Philbert thinks about what grandson Norbert thinks about what brother Egbert thinks about when aunt Roberta is going to lift? Hardly. Rather, I suspect they'd all agree on a rule -- lift after the count of three, perhaps, and trust and hope that the others follow it.
Such rules figure frequently in cooperative behaviour among multiple agents. Another example is the rules of the road. In Carpathia, people drive their horsed carriages on the right -- indeed, it's common knowledge there that people drive them on the right. It would be unwise to drive a carraige in Carpathia unless it were common knowledge -- otherwise, you couldn't be sure that someone wouldn't come from the opposite direction driving on the left, and crash into your carriage head-on. But in Carpathia, do you drive on the right because you are sure the driver of carriage in front knows that the driver of the carriage in front of him knows that the driver in front of him knows to drive on the right? Or do you drive on the right because you know it's the rule in Carpathia to drive on the right, and you hope and trust that other people will follow it? I suspect the latter.
Are these rules just infinitely deep common knowledge by another name? I don't think so. Just because I know "drive on the right" is a rule, this doesn't mean I know, or need to know, that the driver in front knows that the driver two carriages in front knows that the driver behind knows it. Nor does it mean that I should necessarily be able to deduce such a thing. "Drive on the right" is clearly common knowledge of a sort in Carpathia, but it doesn't necessarily have the infinite depth of common knowledge as it is usually defined.
It's not even necessary for all sides to agree on a common rule for deliberate cooperative behaviour to occur. Consider the problem of the two famous Carpathian army generals, Prince Vlad and Prince Nicolae, who must simultaneously attack the Ruthenian army on two different flanks to have any chance of success. If either attacks alone, then the Ruthenian forces will defeat them easily, so it is highly important for the princes to coordinate their strike. But on the day of the attack, the two princes have positioned their armies on different hills, three miles apart. They can only communicate by sending messengers, who take half an hour to cross the difficult and perilous terrain between the hills, which the princes suspect has been penetrated by Ruthenian advance scouts.
In the morning, Vlad, the senior of the two, sends a messenger to Nicolae with the instruction to attack at noon, and a request to send an acknowledgement. Since he cannot be sure that the messenger will get there, his message makes clear that the attack will only go ahead if the acknowledgement is received. Luckily, his messenger completes the journey and delivers the message to Nicolae. Nicolae sends him back with a message of acknowledgement, but also a request to acknowledge his acknowledgement, since he cannot be sure that Vlad knows he received the original message unless his acknowledgement is also acknowledged.
Vlad receives this acknowledgement, and sends an acknowledgement of it as requested. Not to be outsmarted by Nicolae (who is his brother), he also sends a request that his acknowledgement be acknowledged, since he needs to know that Nicolae knows that he knows Nicolae knows when to attack, or otherwise they will be doomed. Upon receiving this message, Nicolae sends an acknowledgement. He also considers requesting that this acknowledgment be acknowledged, but realises that things are now getting a bit silly. He sees that he and Vlad will never be absolutely certain that they will attack simultaneously, and that if they keep sending acknowledgements to each other, they will miss the attack at noon and the Ruthenian army will destroy both of them. At noontime, he will just have to go for it and hope Vlad does too.
Vlad and Nicolae operated on the rule "attack at noon", even though neither could be totally sure that the other agreed on it. They knew about each other's intentions to a certain finite depth, and for practical purposes, that was good enough. It's also good enough for communications software today: Vlad's and Nicolae's communications followed what is known as a four-way handshake protocol, which is as far as I can tell the most elaborate handshake protocol used today (three-way handshaking is much more common, and most often used at critical times like establishing and closing a connection). I claim that the rule "attack at noon" was, in a practical sense, common knowledge between Vlad and Nicolae, even though their mutual knowledge of the rule didn't go infinitely deep.
So although common knowledge definitely goes deeper than "everyone knows", I'm not convinced it ever goes all the way, so to speak. For any practical purpose, one can confidently assign common knowledge a fixed, finite and fairly shallow depth.