Common knowledge is a special kind of knowledge for a group of agents. There is common knowledge of p in a group of agents G when all the agents in G know p, they all know that they know p, they all know that they all know that they know p, and so on ad infinitum.[1] It can be denoted as
CGp
The concept was first introduced in the philosophical literature by David Kellogg Lewis in his study Convention (1969). The sociologist Morris Friedell defined common knowledge in a 1969 paper.[2] It was first given a mathematical formulation in a set-theoretical framework by Robert Aumann (1976). Computer scientists grew an interest in the subject of epistemic logic in general – and of common knowledge in particular – starting in the 1980s. There are numerous puzzles based upon the concept which have been extensively investigated by mathematicians such as John Conway.[3]
The philosopher Stephen Schiffer, in his 1972 book Meaning, independently developed a notion he called "mutual knowledge" (
EGp
EGp
EGEGp\not ⇒ CGp
a
CGKap
CGEGp ⇒ CGp
The idea of common knowledge is often introduced by some variant of induction puzzles (e.g. Muddy children puzzle):
On an island, there are k people who have blue eyes, and the rest of the people have green eyes. At the start of the puzzle, no one on the island ever knows their own eye color. By rule, if a person on the island ever discovers they have blue eyes, that person must leave the island at dawn; anyone not making such a discovery always sleeps until after dawn. On the island, each person knows every other person's eye color, there are no reflective surfaces, and there is no communication of eye color.
At some point, an outsider comes to the island, calls together all the people on the island, and makes the following public announcement: "At least one of you has blue eyes". The outsider, furthermore, is known by all to be truthful, and all know that all know this, and so on: it is common knowledge that he is truthful, and thus it becomes common knowledge that there is at least one islander who has blue eyes (
CG[\existsx\inG(Blx)]
The answer is that, on the kth dawn after the announcement, all the blue-eyed people will leave the island.
The solution can be seen with an inductive argument. If k = 1 (that is, there is exactly one blue-eyed person), the person will recognize that they alone have blue eyes (by seeing only green eyes in the others) and leave at the first dawn. If k = 2, no one will leave at the first dawn, and the inaction (and the implied lack of knowledge for every agent) is observed by everyone, which then becomes common knowledge as well (
CG[\forallx\inG(\negKxBlx)]
\negKa[\forallx\in(G-a)(\negBlx)]
\existsx\in(G-a)(Blx)
For k > 1, the outsider is only telling the island citizens what they already know: that there are blue-eyed people among them. However, before this fact is announced, the fact is not common knowledge, but instead mutual knowledge.
For k = 2, it is merely "first-order" knowledge (
EG[\existsx\inG(Blx)]
For k = 3, it is "second order" knowledge (
EGEG[\existsx\inG(Blx
2[\exists | |
)]=E | |
G |
x\inG(Blx)]
In general: For k > 1, it is "(k - 1)th order" knowledge (
k-1 | |
E | |
G |
[\existsx\inG(Blx)]
In particular:
i | |
E | |
G |
[|G(Blx)|\gej]
i+j\lek
i | |
E | |
G |
[|G(Blx)|\gej]
i-1 | |
E | |
G |
[|G(Blx)|\gej+1]
i | |
E | |
G |
[|G(Blx)|\gej]
j\gek
i+j>k
i | |
E | |
G |
[|G(Blx)|\gej]
i=infty,j=1
Common knowledge can be given a logical definition in multi-modal logic systems in which the modal operators are interpreted epistemically. At the propositional level, such systems are extensions of propositional logic. The extension consists of the introduction of a group G of agents, and of n modal operators Ki (with i = 1, ..., n) with the intended meaning that "agent i knows." Thus Ki
\varphi
\varphi
\varphi
EG\varphi\LeftrightarrowwedgeiKi\varphi,
By abbreviating the expression
EGE
n-1 | |
G |
\varphi
n | |
E | |
G |
\varphi
0 | |
E | |
G |
\varphi=\varphi
C\varphi\Leftrightarrow
infty | |
wedge | |
i=0 |
Ei\varphi
There is, however, a complication. The languages of epistemic logic are usually finitary, whereas the axiom above defines common knowledge as an infinite conjunction of formulas, hence not a well-formed formula of the language. To overcome this difficulty, a fixed-point definition of common knowledge can be given. Intuitively, common knowledge is thought of as the fixed point of the "equation"
CG\varphi=[\varphi\wedgeEG(CG
\aleph0 | |
\varphi)]=E | |
G |
\varphi
\aleph0
\psi
EG(\varphi\wedgeCG\varphi)
\varphi
From this definition it can be seen that if
EG\varphi
\varphi
CGEG\varphi ⇒ CG\varphi
This syntactic characterization is given semantic content through so-called Kripke structures. A Kripke structure is given by a set of states (or possible worlds) S, n accessibility relations
R1,...,Rn
S x S
\pi
Ki\varphi
\varphi
(s,t)\inRi
Ri
RG
CG\varphi
\varphi
(s,t)\inRG
Alternatively (yet equivalently) common knowledge can be formalized using set theory (this was the path taken by the Nobel laureate Robert Aumann in his seminal 1976 paper). Starting with a set of states S. An event E can then be defined as a subset of the set of states S. For each agent i, define a partition on S, Pi. This partition represents the state of knowledge of an agent in a state. Intuitively, if two states s1 and s2 are elements of the same part of partition of an agent, it means that s1 and s2 are indistinguishable to that agent. In general, in state s, agent i knows that one of the states in Pi(s) obtains, but not which one. (Here Pi(s) denotes the unique element of Pi containing s. This model excludes cases in which agents know things that are not true.)
A knowledge function K can now be defined in the following way:
That is, Ki(e) is the set of states where the agent will know that event e obtains. It is a subset of e.
Similar to the modal logic formulation above, an operator for the idea that "everyone knows can be defined as e".
As with the modal operator, we will iterate the E function,
E1(e)=E(e)
En+1(e)=E(En(e))
The equivalence with the syntactic approach sketched above can easily be seen: consider an Aumann structure as the one just defined. We can define a correspondent Kripke structure by taking the same space S, accessibility relations
Ri
Pi
s\inEp
Ep
RG
Pi
i\inG
Common knowledge was used by David Lewis in his pioneering game-theoretical account of convention. In this sense, common knowledge is a concept still central for linguists and philosophers of language (see Clark 1996) maintaining a Lewisian, conventionalist account of language.
Robert Aumann introduced a set theoretical formulation of common knowledge (theoretically equivalent to the one given above) and proved the so-called agreement theorem through which: if two agents have common prior probability over a certain event, and the posterior probabilities are common knowledge, then such posterior probabilities are equal. A result based on the agreement theorem and proven by Milgrom shows that, given certain conditions on market efficiency and information, speculative trade is impossible.
The concept of common knowledge is central in game theory. For several years it has been thought that the assumption of common knowledge of rationality for the players in the game was fundamental. It turns out (Aumann and Brandenburger 1995) that, in two-player games, common knowledge of rationality is not needed as an epistemic condition for Nash equilibrium strategies.
Computer scientists use languages incorporating epistemic logics (and common knowledge) to reason about distributed systems. Such systems can be based on logics more complicated than simple propositional epistemic logic, see Wooldridge Reasoning about Artificial Agents, 2000 (in which he uses a first-order logic incorporating epistemic and temporal operators) or van der Hoek et al. "Alternating Time Epistemic Logic".
In his 2007 book, The Stuff of Thought: Language as a Window into Human Nature, Steven Pinker uses the notion of common knowledge to analyze the kind of indirect speech involved in innuendoes.
The comedy movie Hot Lead and Cold Feet has an example of a chain of logic that is collapsed by common knowledge. The Denver Kid tells his allies that Rattlesnake is in town, but that he [the Kid] has “the edge”: “He's here and I know he's here, and he knows I know he's here, but he doesn't know I know he knows I know he's here.”So both protagonists know the main fact (Rattlesnake is here), but it is not “common knowledge”. Note that this is true even if the Kid is wrong: maybe Rattlesnake does know that the Kid knows that he knows that he knows, the chain still breaks because the Kid doesn't know that.Moments later, Rattlesnake confronts the Kid. We see the Kid realizing that his carefully constructed “edge” has collapsed into common knowledge.