Puzzle

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 they are truthful, and thus it becomes common knowledge that there is at least one islander who has blue eyes (${\displaystyle C_{G}[\exists x\!\in \!G(Bl_{x})]}$). The problem: finding the eventual outcome, assuming all persons on the island are completely logical (every participant's knowledge obeys the axiom schemata for epistemic logic) and that this too is common knowledge.

Solution

The answer is that, on the kth dawn after the announcement, all the blue-eyed people will leave the island.^[5]

Modal logic (syntactic characterization)

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 K_i (with i = 1, ..., n) with the intended meaning that "agent i knows." Thus K_i ${\displaystyle \varphi }$ (where ${\displaystyle \varphi }$ is a formula of the logical calculus) is read "agent i knows ${\displaystyle \varphi }$." We can define an operator E_G with the intended meaning of "everyone in group G knows" by defining it with the axiom

${\displaystyle E_{G}\varphi \Leftrightarrow \bigwedge _{i\in G}K_{i}\varphi ,}$

By abbreviating the expression ${\displaystyle E_{G}E_{G}^{n-1}\varphi }$ with ${\displaystyle E_{G}^{n}\varphi }$ and defining ${\displaystyle E_{G}^{0}\varphi =\varphi }$, common knowledge could then be defined with the axiom

${\displaystyle C\varphi \Leftrightarrow \bigwedge _{i=0}^{\infty }E^{i}\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" ${\displaystyle C_{G}\varphi =[\varphi \wedge E_{G}(C_{G}\varphi )]=E_{G}^{\aleph _{0}}\varphi }$. Here, ${\displaystyle \aleph _{0}}$ is the Aleph-naught. In this way, it is possible to find a formula ${\displaystyle \psi }$ implying ${\displaystyle E_{G}(\varphi \wedge C_{G}\varphi )}$ from which, in the limit, we can infer common knowledge of ${\displaystyle \varphi }$.

From this definition it can be seen that if ${\displaystyle E_{G}\varphi }$ is common knowledge, then ${\displaystyle \varphi }$ is also common knowledge (${\displaystyle C_{G}E_{G}\varphi \Rightarrow C_{G}\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 ${\displaystyle R_{1},\dots ,R_{n}}$, defined on ${\displaystyle S\times S}$, intuitively representing what states agent i considers possible from any given state, and a valuation function ${\displaystyle \pi }$ assigning a truth value, in each state, to each primitive proposition in the language. The Kripke semantics for the knowledge operator is given by stipulating that ${\displaystyle K_{i}\varphi }$ is true at state s iff ${\displaystyle \varphi }$ is true at all states t such that ${\displaystyle (s,t)\in R_{i}}$. The semantics for the common knowledge operator, then, is given by taking, for each group of agents G, the reflexive (modal axiom T) and transitive closure (modal axiom 4) of the ${\displaystyle R_{i}}$, for all agents i in G, call such a relation ${\displaystyle R_{G}}$, and stipulating that ${\displaystyle C_{G}\varphi }$ is true at state s iff ${\displaystyle \varphi }$ is true at all states t such that ${\displaystyle (s,t)\in R_{G}}$.

Set theoretic (semantic characterization)

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, P_i. This partition represents the state of knowledge of an agent in a state. Intuitively, if two states s₁ and s₂ are elements of the same part of partition of an agent, it means that s₁ and s₂ are indistinguishable to that agent. In general, in state s, agent i knows that one of the states in P_i(s) obtains, but not which one. (Here P_i(s) denotes the unique element of P_i 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:

${\displaystyle K_{i}(e)=\{s\in S\mid P_{i}(s)\subset e\}}$

That is, K_i(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".

${\displaystyle E(e)=\bigcap _{i}K_{i}(e)}$

As with the modal operator, we will iterate the E function, ${\displaystyle E^{1}(e)=E(e)}$ and ${\displaystyle E^{n+1}(e)=E(E^{n}(e))}$. Using this we can then define a common knowledge function,

${\displaystyle C(e)=\bigcap _{n=1}^{\infty }E^{n}(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 ${\displaystyle R_{i}}$ that define the equivalence classes corresponding to the partitions ${\displaystyle P_{i}}$, and a valuation function such that it yields value true to the primitive proposition p in all and only the states s such that ${\displaystyle s\in E^{p}}$, where ${\displaystyle E^{p}}$ is the event of the Aumann structure corresponding to the primitive proposition p. It is not difficult to see that the common knowledge accessibility function ${\displaystyle R_{G}}$ defined in the previous section corresponds to the finest common coarsening of the partitions ${\displaystyle P_{i}}$ for all ${\displaystyle i\in G}$, which is the finitary characterization of common knowledge also given by Aumann in the 1976 article.