What Lewis's common knowledge is and what it is not

David Lewis is usually attributed to have been the first person explicitly defining common knowledge. Though, what David Lewis defined as "common knowledge" in his dissertation "Convention" is not what people in philosophy, game theory, computer science, ... usually take it to be.

So, what then is common knowledge usually taken to be, or more precisely, common knowledge among a group G of agents that p (p being a proposition)?

The basic idea of many proposals is that there is common knowledge among a group G of agents that p iff for all agents A,A' of G:

• A knows that p, and
  
• A knows that A' knows that p, and
  
• A knows that A' knows that A knows that p, and
• so on, ad infinitum.
  

Many think (whether correctly or incorrectly) that the notion of common knowledge is central in explanations of social phenomena. For example, it has been proposed that because of there being common knowledge, people can coordinate their behavior when they want to do so. It has also interesting consequences in strategic interactions, when I know that you know ... what I know. In such cases, my strategy choice should better take this information into account. I shouldn't reckon that because you don't know (or don't know that I know ... what I know), I might be successful in manipulating you.

That has motivated a lot of research - and produced in part the misunderstanding I alluded to in the introduction. To have some handy names, let us call Lewis's notion "Lewis common knowledge" or "common reason to believe" and common knowledge in the sense of what people in the field usually take it to be "Aumann-style common knowledge".

One characteristic of Aumann-style common knowledge is that it is factive. That is, if a group has common knowledge (in Aumann's sense) that p, then p is the case. As we will see, this is not true for common knowledge in Lewis's sense. It is possible that in a group it is common knowledge (in Lewis's sense) that p, and yet p is false.

Though, it is understandable why people usually think that Lewis common knowledge is factive. After all, we expect that any definition of common knowledge should capture the basic idea outlined above. Since common knowledge in this sense is a combination of individual knowledge and such knowledge is generally taken to be factive, it is clear why people have this opinion.

Nevertheless, the point is that this is not true for Lewis's notion. The point is important because criticism against application of Aumann-style common knowledge does then necessarily carry over to Lewis common knowledge. Moreover, there are actually some mathematical formalizations of Lewis's notion which ignore this fact. Whatever they are formalizations of, they are not formalizations of Lewis's notion. Andreas Kemmerling is, to my knowledge, the only person who has ever made the point that Lewis common knowledge is not a kind of knowledge - and very clearly so! For some reason, Kemmerling's contribution has not been appreciated.

Before going through some differences between Aumann-style common knowledge and Lewis common knowledge, I'd like to point to some typical examples from the literature.

Some Examples in the literature

The concept was first introduced in the philosophical literature by David Kellogg Lewis in his study Convention (1969). It has been first given a mathematical formulation in a set-theoretical framework by Robert Aumann (1976).

(http://en.wikipedia.org/wiki/Common_knowledge_(logic), accessed 2008-10-08)

Folk knowledge is not factive as we know! The quote suggests that one at the same concept has been "formulated" in different ways. This would preclude that whether the claim that common knowledge is factive comes out true depends on the used "formulation".

Along similar lines also the Nobel prize committee suggests this:

In his paper “Agreeing to disagree” (1976), Aumann introduced to game theory the concept of “common knowledge,” a concept first defined by Lewis (1969). An event is common knowledge among the players of a game if it is known by all players, if all players know that it is known by all players, if all players know that all players know that it is known by all players etc., ad infinitum.

(The Royal Swedish Academy of Sciences: "Robert Aumann’s and Thomas Schelling’s Contributions to Game Theory: Analyses of Conflict and Cooperation", URL: http://nobelprize.org/nobel_prizes/economics/laureates/2005/ecoadv05.pdf, p. 20, last accessed: 2008-10-08)

And last but not least, we find it also in the Stanford Encyclopedia of Philosophy:

Yet it was David Lewis (1969) who first gave an explicit analysis of common knowledge in the monograph Convention. Stephen Schiffer (1972), Robert Aumann (1976), and Gilbert Harman (1977) independently gave alternate definitions of common knowledge. Jon Barwise (1988, 1989) gave a precise formulation of Harman's intuitive account. Schiffer's analysis of common knowledge as a hierarchy of epistemic claims has become standard in the philosophical and social science literature. Lewis', Aumann's, and Barwise's accounts all imply the hierarchical account. In some contexts, Schiffer's, Aumann's, and Barwise's definitions of common knowledge are more convenient to use than Lewis' original definition. More recently, Margaret Gilbert (1989) proposed a somewhat different account of common knowledge which she argues is preferable to the standard account.

(Vanderschraaf, Peter and Sillari, Giacomo: "Common Knowledge", The Stanford Encyclopedia of Philosophy (Fall 2008 Edition), Edward N. Zalta (ed.), URL: http://plato.stanford.edu/archives/fall2008/entries/common-knowledge/)

I hope you agree that what Vanderschraaf and Sillari suggest is that one and the same thing was defined in different ways and that the only relevant differences between these definitions relate to their "convenience" when working with them.

Some differences between an Aumann-style definition and Lewis's definition

One of the characteristics of Aumann's definition is that "common knowledge in a group G that p" is defined as a non-primitive set-theoretic operator CK (for some group G assumed to be fixed). The operator is defined as a truth-preservative combination of individual knowledge that p. Individual knowledge is factive. Thus, common knowledge is factive.

Formal digression
A little bit more formally, propositions p are subsets of the set of possible worlds Omega. The individual knowlege operator Ki for an agent i is an operator from the powerset of Omega to the powerset of Omega. Ki maps propositions p to propositions p' of worlds in which i knows that p obtains. Agent i is said to have individual knowledge that p in world w iff w is an element of Ki(p).

For operators Ki the following axiom holds:

(F) For all agents i, for all propositions p: Ki(p) -> p.

Axiom (F) expresses that if an agent has individual knowledge that p, then p is the case. From the fact that common knowledge is a truth-preservative combination of individual knowledge it follows that the following is a theorem: For all propositions p: CK(p) -> p. This theorem expresses that if a group has common knowledge about some proposition p, then p is the case.

Back to topic
So, clearly, Aumann-style common knowledge is factive. I claimed that Lewis common knowledge is not. To see this, let us recall Lewis's definition:

A proposition p is common knowledge in the group G if a state of affairs A obtains such that

1. Everyone in G has reason to believe that A holds;
2. A indicates to everyone in G that everyone in G has reason to believe that A holds;
3. A indicates to everyone in G that p.

Assume that a group has Lewis common knowledge that p. What does follow from this? - Well, let us unpack the definition. Thereby we can reason that a state of affairs A obtained such that conditions 1. to 3. are satisfied.

Now observe that the knowledge is nowhere mentioned or used. The only epistemic states which are ascribed to agents in G are having reasons to believe and indications. So, clearly, if Lewis common knowledge were factive, then it would derive from one of these ascriptions.

Though, some agent i having a reason to belief that p does not even imply that i actually believes that p. This does only follow, according to Lewis, if we additionally assume that i is rational (in some sense to be explicated). "i has a reason to believe that p in a situation s" means roughly that i is in s in a situation in which she would be justified to believe that p if she believed that p in s. And even if we assume common rationality (that is, everyone is rational in the required sense and assumes that that everyone is rational in this sense and so on...), all we can derive is that agents in G believe that p. But beliefs are not factive.

What about the indications? And what is it to indicate something to someone anyway? - According to Lewis,

[l]et us say that A indicates to someone x that ___ if and only if, if x had reason to believe that A held, x would thereby have reason to believe that ___.

Without going into the details of this notion, observe that the only epistemic notion is - again - having a reason to believe. That is, we can't derive knowledge from indications either. Thus, it does not follow that Lewis common knowledge is factive.

To conclude, Lewis common knowledge is not the same as Aumann-style common knowledge. Once we realize this we can start asking another set of questions about Lewis common knowledge. I mentioned above that applications of Aumann-style common knowledge have been criticized. Now, an interesting question is whether Lewis common knowledge can do the jobs Aumann-style common knowledge is supposed to do and whether it can escape the criticism. Thrilling! Though, this is material for another post.

Update: Correction due to Lars' observation.