Common Knowledge Logic

Origin. Lewis (1969), Aumann (1976). Knowledge shared by all and known to be shared. Fixed point: everyone knows everyone knows... Foundation for coordination and convention.

Models. Kripke structures with multiple agents. Common knowledge C: infinite conjunction of nested knowledge. Fixed point characterization.

Formalism.

Operators: Kᵢφ: agent i knows φ Eφ: everyone knows φ (E = ∧ᵢKᵢ) Cφ: common knowledge of φ

Everyone knows: Eφ ≡ K₁φ ∧ K₂φ ∧ ... ∧ Kₙφ

Common knowledge: Cφ ≡ Eφ ∧ EEφ ∧ EEEφ ∧ ... Infinite conjunction of iterated everyone-knows.

Fixed point: Cφ ↔ E(φ ∧ Cφ) Common knowledge is greatest fixed point.

Semantics: Define ~ᵢ as indistinguishability for agent i. ~_E = ∪ᵢ~ᵢ (union) _C = (_E)* (transitive closure) M, s ⊨ Cφ iff ∀t. s ~_C t implies M, t ⊨ φ

Distributed knowledge: Dφ: distributed knowledge (intersection) What agents would know if they pooled information. ~_D = ∩ᵢ~ᵢ

Example: "Coordinated attack problem" C(attack at dawn) needed for coordination. Cannot achieve via finite message exchange.

Symbols.

Metatheory. C_G is interpreted by the reflexive transitive closure of the union of the agents' relations, and its axiomatization needs both the fixed-point axiom Cφ → E(φ ∧ Cφ) and the induction rule: from ⊢ ψ → E(φ ∧ ψ) infer ⊢ ψ → Cφ. With these, S5ₙ with common knowledge is weakly complete and has the finite model property, so validity is decidable; Halpern and Moses (1992) proved satisfiability EXPTIME-complete for two or more agents, against PSPACE-complete for the same systems without C. Model checking is a different matter: on an explicit finite model C_G is evaluated by taking a transitive closure, so it runs in polynomial time. C is not definable in the multi-agent epistemic language — no finite formula is equivalent to it — which is why the fixed-point machinery is required rather than convenient. Halpern and Moses (1990) proved that common knowledge cannot be attained in an asynchronous system, nor by communication over a channel that may lose messages, which is the exact content of the coordinated attack problem.

Applies to. Game theory. Conventions. Coordination problems. Distributed systems. Social epistemology.

Limitations. The logic is not compact: {Eφ, EEφ, EEEφ, ...} together with ¬Cφ is finitely satisfiable and unsatisfiable, so no finitary Hilbert system is strongly complete and completeness holds only for the empty premise set. Common knowledge is unattainable in fact as well as in principle — by Halpern and Moses (1990), in a system without simultaneous events, or with any possibility of message loss, no contingent proposition ever becomes common knowledge, so the coordination arguments that presuppose it describe a limit case rather than a state. Adding C raises satisfiability from PSPACE to EXPTIME, and combining it with perfect recall over time makes validity Π¹₁-complete (Halpern and Vardi, 1989), hence not recursively axiomatizable at all. The account inherits logical omniscience from Kᵢ, and it treats a group as a set of relations, so it says nothing about the shared salience that generates common knowledge in Lewis's original argument.

© 2026 Lingenic LLC