Adding common knowledge

Using the language $\mathcal{L}_N^K$ it is possible to express that some agent knows a certain fact, or an agent knows that another agent knows that he knows some fact, and so on. However, for a number of situations this language is not expressive enough: the state of knowledge in certain situations can only be described by an infinite number of iterations: everyone (in a group) knows simultaneously a fact $\alpha$, everyone knows that everyone knows $\alpha$, everyone knows that everyone knows that everyone knows $\alpha$, and so on. In such a case we say that $\alpha$ is common knowledge among the group.

Common knowledge turns out to be a crucial concept in in explaining the rationality of certain actions, namely those co-operative enterprises such as conventional social practices, including language. It was first studied by David Lewis in the context of convention ([Lew69]), who observes that in order for something to be a convention, it must be common knowledge in the group. The notion has subsequently been applied to the analysis of language and discourse understanding ([Sch72], [CM81]), of games ([Aum76], [Gea92]), and of distributed systems ([Hal87]).

Current theories of intelligent agents usually take an agent-centric viewpoint, i.e., agents are viewed from the perspective of the designer of a single agent. Therefore, individual knowledge is of far greater interest than common knowledge. Nevertheless, the concept of common knowledge is of interest because it raises problems about the complexity of cognitive states which we can sensibly attribute to each other.

Although we could define common knowledge for each nonempty subset of the set $Agt$ of agents, for simplicity we consider only common knowledge of the whole group. The language $\mathcal{L}_N^{CK}$ of epistemic logic with common knowledge is obtained by adding a new operator $C$ to the language $\mathcal{L}_N^K$. The formula $C\alpha$ is interpreted as: ``$\alpha$ is common knowledge of the agents''. Formally, $\mathcal{L}_N^{CK}$ is defined as follows:

The auxiliary operator $E$ (to be interpreted as ``everyone knows'') is defined as:

$$E\alpha =_{def} K_{1}\alpha \land \ldots \land K_{N}\alpha$$

Logics of common knowledge can be axiomatized on the basis of the corresponding epistemic logics by adding suitable axiom schemata and inference rules. The following axiomatization is due to Halpern and Moses ([HM92]).

Various other axiomatizations exist, e.g., by Kraus and Lehmann ([KL88]), Lismont ([Lis93]), Lismont and Mongin ([LM94]), and Bonanno ([Bon96]).

Logics of common knowledge can be given an adequate possible worlds semantics (cf., e.g., [KL88], [HM92], [FHMV95]). As in definition 3, each knowledge operator is interpreted by means of a binary relation on the set of possible worlds. An additional alternativeness relation is introduced to interpret the common knowledge operator. To capture the relationship of individual and common knowledge, it is stipulated that the relation corresponding to the common knowledge operator is the transitive closure of the union of the accessibility relations which correspond to the knowledge operators. Formally:

A model is said to have a certain property if the accessibility relations $R_1,\ldots,R_N$ have that property. (Note that $R^+$ needs not necessarily have that property.) The following theorem ([FHMV95]) lists some well-known completeness results about logics of common knowledge.