When WhatsApp released the blue-tick read-receipt feature, it was followed by jokes about seemingly ridiculous extensions of the feature. If I send a message to you, the blue tick tells me that you saw the message. In its next feature, WhatsApp can perhaps send another message to you saying that I saw the blue tick so that you know that I know that you received the message. And then it can send another message to me letting me know that you know that I know that you received the message. And this can continue ad infinitum. This apparently funny and benign hierarchy of information is actually at the heart of an unsolvable problem known as the coordinated attack problem. It has a few strong consequences; it partially explains why we have open secrets that everyone knows yet no one acts on it; and why people tolerate bad authorities for a long time even after everyone knows that the authority is bad and should be ousted, and why do sociological changes seem to take a long time. At a deeper level, this information hierarchy is central to how values are formed and destroyed in human societies. The blue-eyed islander puzzle illustrates how complex this hierarchy can be.
In game theory, if you and I know something, it is called mutual knowledge (of first order) between us. If I know that you know and you know that I know, it is called mutual knowledge of the second order. And If I know that you know that I know and you know that I know that you know :D, it is mutual knowledge of the third order. This can be confusing, but think of it in the context of a card game, assuming that we are talking about knowing what card I have. Each layer of the information Hierarchy has a different implication on the game — they are all different. At this point if you are reminded of a sequence from the TV series F.R.I.E.N.D.S, yes, that is exactly what I am talking about. The infinite-order mutual knowledge is called common knowledge. If I have a piece of news X, and I call up 10 of my friends individually and give them the news, then it is a first-order mutual knowledge of these 10 people. Each of them know, but none of them are sure if the remaining 9 know. Instead, if I bring them all in a room and announce it, then X is a common knowledge of these 10 people. In this case, they all heard it together, so they all know, they know that everyone else knows, they know that everyone knows that everyone else knows.. you get the point. If you have attended conferences, you might think about the difference between a talk and a poster in this context.
Consider a village with 100 people and a village head. Let us suppose that the village head is bad in some way and needs to be ousted. Let us also assume that this requires all 100 people to revolt at the same time and if any one of them doesn’t revolt, the revolt will be suppressed. Practically, it is more likely that only about 50 of them need to revolt, but we can go with this for the purpose of argument. What level of mutual knowledge of the fact that the village head is bad do we need here? If everyone individually knows that the head is bad, that is not really sufficient for a revolt — no one wants to be the only one revolting. Therefore no one revolts, unless they are certain that everyone else will revolt too. Therefore, everyone needs to know that everyone else knows that the head is bad. And, to be sure that everyone else revolts, everyone needs to know that everyone else knows that everyone knows that the head is bad and ad infinitum. Strictly speaking, no finite order of mutual knowledge is sufficient for a revolt. This is the coordinated attack problem. Practically, revolts don’t happen until the mutual knowledge has reached a sufficiently high order. The coordinated attack problem is often presented with the two-party example: two military convoys coordinating an attack from different places. This will need the information of the attack time to be a common knowledge between the two. These examples are interesting, but the principle is far more general — it applies to any action that requires a coordinated effort. Information wouldn’t be actionable unless it has reached a high order of mutual knowledge. Indeed, an effective way to control riots is to prevent public gatherings — which only prevents information from being shared at higher levels of the hierarchy, while allowing it to spread at lower levels.
One can imagine that the villagers not revolting is an equilibrium, that keeps things stable; all villagers revolting is also an equilibrium, perhaps a more desirable one. But only some of them revolting is a non-equilibrium state, worse than both the equilibria. This is a system with two local equilibria, much like the Stag hunt problem in game theory. In the stag hunt problem, two hunters, with an arrow each are approaching a pair of rabbits from opposite directions. They can’t communicate directly. If they both target the rabbits, each of them will get a rabbit. However, one of them spots a stag, for which, they need 2 arrows, i.e., both of them need to shoot simultaneously. A coordinated attack on the stag is obviously better than carrying on with targeting the rabbits; however, this needs a common knowledge of the presence of the stag. It is not sufficient even if both the hunters spot the stag; each of them needs to know that the other has seen the stag; and that the other knows that they have spotted the stag and so on. If only one of the hunters attacks the stag, then it runs away and the hunter gets nothing.
We can generalize the stag hunt problem to n hunters with one arrow each targeting n rabbits, and a stag walks in where one needs to shoot m arrows. This will mean that shooting at the stag is desirable only when there is a subset of at-least m hunters for whom the presence of the stag is common knowledge. The above two examples appear to be about revolts and stag hunting; however, the former can be thought of as a representation of a society destroying an old value and the latter, as a society changing a value.
Thought Flow 