Common Knowledge (Convention)

The infinite hierarchy of mutual expectation introduced by Lewis (1969) and rediscovered by Aumann (1976) in game theory and Halpern–Moses (1990) in distributed systems: A knows p, A knows that B knows p, A knows that B knows that A knows p, … all the way up. A convention is sustained by common knowledge of the regularity. The construction has the same mathematical content in three independent fields — Lewis-style social philosophy, game theory, and distributed-systems epistemology — and is unattainable in fully asynchronous distributed systems (Halpern & Moses), with deep consequences for what coordination protocols can achieve.

In this vault

Backlinks

Linked Pages

Mutual Expectation

The infinite hierarchy of expectations that sustains a Convention (Lewis): each party expects others to follow R, expects others to expect them to follow R, and so on. Equivalent to (and rediscovered as) common knowledge in game theory and distributed systems. The operative epistemic condition that makes a regularity self-sustaining without explicit agreement.

In this vault

Knowledge and Common Knowledge in a Distributed Environment

Reference

Halpern, J. Y., & Moses, Y. (1990). “Knowledge and Common Knowledge in a Distributed Environment.” Journal of the ACM, 37(3), 549-587. URL

Summary

Halpern and Moses recast distributed protocol design as knowledge transformation: sending a message changes the knowledge state of the system, and correctness specifications can be stated in terms of what individual processes, groups, or “the system” know at various points. The paper develops a formal epistemic logic for distributed systems with operators K_i (agent i knows), E (everyone knows), and C (common knowledge — everyone knows that everyone knows, to infinite depth).

The central technical result is striking: in a truly asynchronous distributed system, common knowledge is unattainable. The classical “coordinated attack” problem (two generals must attack simultaneously but communicate only via lossy messengers) is unsolvable because simultaneous action requires common knowledge of the time to attack, and no finite message chain ever reaches the fixpoint. The muddy children puzzle — a beloved epistemic set piece walked through in the opening — shows how a public announcement can create common knowledge that sequential private reasoning cannot, illuminating why synchronous broadcast matters.

Because strict common knowledge is unattainable, the paper introduces and characterises weaker variants: eventual common knowledge, ε-common knowledge (bounded delay), timestamped common knowledge, and concurrent common knowledge. Each corresponds to a different system model (synchronous, partially synchronous, etc.) and a different class of solvable coordination tasks. This framework turned “what does a protocol achieve?” into a precise epistemic question and seeded the entire field of Theoretical Aspects of Reasoning about Knowledge (TARK).

Key Ideas

Epistemic hierarchy: distributed knowledge ⊑ someone knows ⊑ everyone knows (E) ⊑ common knowledge (C).
Common knowledge (C): fixpoint E^ω — needed for any simultaneous coordinated action.
Coordinated attack / muddy children: canonical illustrations of how public announcements create C.
Impossibility: in async or even synchronous-with-uncertain-delivery systems, C cannot be attained by message exchange.
Weakenings: ε-C (bounded-time C), eventual C, timestamped C, concurrent C — each aligned with a synchrony assumption.
Protocols as knowledge transformers: specifications are claims about K_i, E, C; message sends are knowledge updates.
Runs-and-systems semantics: each global history is a “run”; agent’s knowledge is the set of runs it cannot distinguish from the actual one.

Connections

Epistemic Logic
Epistemic S5
Knowing What vs Knowing That
The Synthesis of Digital Machines with Provable Epistemic Properties — Rosenschein-Kaelbling operationalise this framework.
Time Clocks and the Ordering of Events in a Distributed System — the “local history” underpinning indistinguishable runs is Lamport’s past-cone.
Impossibility of Distributed Consensus with One Faulty Process — consensus impossibility has an epistemic reading: common knowledge of a decision cannot be attained.
CAP Theorem

Conceptual Contribution

Convention (Lewis)

David Lewis’s (1969) game-theoretic analysis of conventions: a regularity R in the behaviour of a population is a convention iff almost everyone conforms to R, almost everyone expects almost everyone else to conform, almost everyone prefers conforming on the assumption that others conform, and some alternative regularity could equally have served. Sustained by Mutual Expectation / common knowledge. Foundational analysis of how shared meaning, currency, and social roles arise without explicit agreement.

In this vault

Convention - Lewis

Convention: A Philosophical Study

Reference: Lewis, D. K. (1969). Convention: A Philosophical Study. Harvard University Press, Cambridge MA. (Reprinted 2002, Blackwell.) SEP entry on Convention · Wiley publisher page (book; no full-text OA.)

Summary

Lewis offers the first rigorous game-theoretic analysis of how shared conventions — including, paradigmatically, the conventions of language — arise and sustain themselves among rational agents without explicit agreement. The book opens by defining a coordination problem: a situation in which several agents have multiple equilibria available, all parties prefer reaching some equilibrium to none, and they are largely indifferent (or have non-conflicting preferences) over which equilibrium they reach. Lewis’s central thesis is that a convention is a regularity in behaviour that is one solution to a coordination problem, sustained by mutual expectation — each party expects the others to follow the regularity, expects the others to expect them to follow it, and so on up an infinite hierarchy that Lewis was the first to formalise as common knowledge. The book applies this analysis to driving conventions (drive on the right vs left), signalling, currency, and at length to language: the conventions of meaning are coordination equilibria sustained by mutual expectation in a population of speakers; semantic content is what would be the case if the convention were followed. Lewis’s framework supplies the philosophical foundation for every later treatment of emergent and negotiated meaning — emergent-communication research in MAS and deep learning, the ACL evolution programme, and the language-games tradition (Wittgenstein operationally, Steels formally) all proceed in the conceptual space Lewis defined. The common-knowledge construction is independently a foundational result for distributed-systems theory (Halpern & Moses 1990) and game theory (Aumann 1976).

Key Ideas

Coordination problem: a strategic situation with multiple Pareto-comparable equilibria where no party prefers a non-equilibrium outcome and the parties’ preferences over equilibria largely coincide. The classical examples — driving side, meeting place — generalise to language, money, social roles.
Convention as a self-sustaining regularity: a regularity R is a convention iff (i) almost everyone conforms to R, (ii) almost everyone expects almost everyone else to conform to R, (iii) almost everyone prefers conforming on the assumption that others conform, and (iv) some alternative regularity could have been the convention instead (no party of the convention is intrinsically preferred).
Common knowledge: the infinite hierarchy of mutual expectation that sustains a convention — A knows that B follows R; A knows that B knows that A follows R; and so on. Lewis was the first to give a formal account of this in social terms; the construction was rediscovered by Aumann in game theory and Halpern–Moses in distributed systems.
Salience and precedent as convention selectors: when multiple equilibria are available, salient features (Schelling’s focal points, see The Strategy of Conflict) and historical precedent select among them. There is no rationality-driven argument for which equilibrium becomes conventional; the answer is contingent on saliency.
Language as convention: meaning is what would obtain if the convention were followed. Truth-conditions, communicative force, and reference are all conventionally fixed — but the convention is not arbitrary, it is sustained by everyone’s expectation that everyone else will use words a particular way.
Conventions vs explicit agreements: Lewis argues that explicit agreement is neither necessary nor sufficient for convention — many conventions arise without agreement (precedent does the work) and many agreements never become conventions (because mutual expectation does not develop).
Population vs pair: conventions are population-level facts; one cannot have a convention with a single partner. Mutual expectation must extend across the relevant community for the regularity to be convention-grade.

Connections

Conceptual Contribution

Claim: Conventions — including the conventions of language — are best analysed as solutions to coordination problems sustained by mutual expectation (formally, common knowledge) in a population of rational agents. There is nothing arbitrary about the convention’s function, but the particular regularity that becomes conventional is contingent on salience, precedent, and historical accident.
Mechanism: Game-theoretic analysis of coordination problems with multiple equilibria; definition of convention via four clauses (conformity, mutual expectation, conditional preference, alternativeness); explicit construction of common knowledge as an infinite hierarchy of expectations; application to driving conventions, signalling, currency, and at length to language semantics.
Concepts introduced/used: Coordination Game, Convention (Lewis), Common Knowledge (Convention), Mutual Expectation, Focal Point (via dialogue with Schelling), Salience, Precedent, Convention vs Agreement.
Stance: foundational philosophical monograph.
Relates to: Direct philosophical foundation for every later treatment of emergent meaning and negotiated language: Steels’ language games are operational realisations of Lewis’s coordination-problem analysis with explicit interaction protocols; Lazaridou et al. and the deep-learning emergent-communication line train neural agents to converge on Lewis-style conventions in referential games. The ACL-evolution programme (Toward Automated Evolution of ACLs, Towards Automating the Evolution of Linguistic Competence) treats the ACL itself as an evolving Lewis-convention. Lewis’s common-knowledge construction is independently the foundation of Halpern & Moses 1990 in distributed systems and Aumann (1976) in game theory — distributed protocols and conventional language share the same mathematical object. The framework also clarifies what is at stake in the Mentalistic Semantics vs Public Semantics debate in ACLs: Lewis-style conventions are public-semantics objects (mutual-expectation regularities) but their stability depends on something close to mentalistic conditions (each agent’s expectations about others’ beliefs), so the two semantic families are dual aspects of the same phenomenon rather than competitors. Why AI Agents Communicate In Human Language revisits Lewis from the LLM-agent angle: natural language is a particular Lewis-convention (a contingent equilibrium) and not necessarily the optimal one for inter-agent coordination.