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.

Symbol	Unicode	Name	Meaning
Kᵢ	—	Knows	Agent i knows
E	—	Everyone	All know
C	—	Common	Common knowledge
D	—	Distributed	Pooled knowledge

Metatheory. Axiomatizable with fixed-point rule. Complete for common knowledge. EXPTIME model checking. Not finitely axiomatizable without rule.

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

Limitations. Idealized rationality. Finite communication insufficient. Common knowledge hard to achieve. Computational complexity.