Common Knowledge

Common knowledge is defined by infinite recursion. It is not enough that everyone knows a fact (E-knowledge). For a fact p to be common knowledge among a group, the following must hold:

• Everyone knows p.
• Everyone knows that everyone knows p.
• Everyone knows that everyone knows that everyone knows p.
• And so on, ad infinitum.

This creates a public event where the fact is completely transparent and no agent can entertain the possibility that another might be unaware. This is often formalized using the knowledge operator K and the common knowledge operator C, where C(p) implies K_i(p), K_i(K_j(p)), K_i(K_j(K_k(p))), etc., for all agents i, j, k.

Common knowledge is essential for establishing social conventions and enabling coordinated action where unilateral deviation is harmful. Classic examples include:

• Traffic Lights: The rule 'red means stop' is not just known by all drivers; each driver knows that all others know it, and knows that others know they know it. This mutual certainty enables safe coordination.
• The Coordinated Attack Problem: Two generals must synchronize an attack. Without a message that is guaranteed to be received (creating common knowledge of the plan), they cannot coordinate, as each will fear the other did not get the message.
• Market Conventions: The value of fiat currency or a corporate logo relies on common knowledge of their shared meaning within a society.

Common knowledge is typically generated through public events or announcements. The key mechanism is that the announcement itself is witnessed by all agents, and this witnessing is also public.

• Physical Copresence: A speaker declaring p to a gathered crowd, where everyone sees everyone else hearing it, can generate common knowledge of p.
• Synchronous Broadcast: A national television address, where it is common knowledge that everyone is watching the same channel at the same time, can create common knowledge of the announcement's content.
• The Email Paradox: Sending an email to a group does not generate common knowledge of its contents, as recipients cannot be sure others have read it. Follow-up 'reply-all' confirmations can asymptotically approach it but do not guarantee infinite recursion.

A critical distinction is between common knowledge and mutual knowledge (or shared knowledge).

• Mutual Knowledge (E-knowledge): A fact p is mutual knowledge if everyone in the group knows p. Formally: E(p) = K_1(p) ∧ K_2(p) ∧ ... ∧ K_n(p). The recursion stops at the first level.
• Common Knowledge (C-knowledge): As defined, requires the infinite recursion: C(p) = E(p) ∧ E(E(p)) ∧ E(E(E(p))) ∧ ...

Many coordination failures occur because agents have only mutual knowledge, not common knowledge. For example, in a guess-the-average game, if players are told 'the number is between 0 and 100,' that is mutual knowledge. If they are told 'this fact is known by all,' it becomes common knowledge, dramatically changing the rational outcome (often to 0).

Common knowledge is rigorously modeled using multi-agent epistemic logic.

• Knowledge Operator (K_i): K_i(p) means 'agent i knows that p is true.'
• Everybody Knows Operator (E): E(p) = ∧_i K_i(p) (the conjunction of knowledge across all agents).
• Common Knowledge Operator (C): C(p) is defined as the fixed point of the equation: C(p) ↔ E(p ∧ C(p)). This means p is common knowledge if everyone knows both p and that p is common knowledge.
• Axiomatization: Common knowledge satisfies the axioms of knowledge (Truth, Positive Introspection, Negative Introspection) plus two key rules:
  • Fixed Point Axiom: C(p) → E(p ∧ C(p))
  • Induction Rule: If p → E(p ∧ q) is valid, then p → C(q) is valid. This rule allows common knowledge to be generated from a publicly known implication.

In AI and distributed computing, common knowledge is a practical engineering concern.

• Distributed Consensus Protocols: Algorithms like Paxos or Raft aim to create common knowledge of a decided value across a server cluster. A message is only 'committed' when it becomes common knowledge among a quorum that it has been accepted.
• Blockchain and Ledgers: A blockchain's immutable, public ledger is designed to create common knowledge of the transaction history. Every participant knows the state, and knows that all others know the same state, preventing double-spend disputes.
• Multi-Agent Planning: For agents to commit to a joint plan, they often require common knowledge of the plan's adoption. Without it, an agent may defect, fearing others will defect first.
• Game Theory Equilibria: The rationality assumptions underpinning solution concepts like Nash Equilibrium often implicitly assume common knowledge of the game's rules and of the players' rationality.

Mutual belief describes a state where a proposition P is believed by all agents in a group, and each agent believes that all others believe P. However, unlike common knowledge, this recursive belief does not extend to infinite depth. It is a weaker, finite-level construct. For example, in a team, there may be a mutual belief about the project deadline, but not necessarily an infinite recursion of that belief.

• Key Distinction: Stops at a finite level of recursion (e.g., 'I believe you believe I believe P').
• Practical Use: Often sufficient for initiating coordinated action in many real-world scenarios where infinite recursion is computationally or cognitively implausible.

Multi-agent epistemic logic is the formal logical framework used to rigorously reason about knowledge and belief among multiple intelligent agents. It extends modal logic with operators like K_i(P) (agent i knows P) and E_G(P) (everyone in group G knows P). It provides the mathematical machinery to define and prove properties about common knowledge (C_G(P)) and mutual belief.

• Core Operators: Knowledge (K), Belief (B), Common Knowledge (C), Distributed Knowledge (D).
• Application: Used to specify and verify protocols in distributed systems, cryptographic protocols, and game theory, where the states of knowledge directly affect outcomes.

Higher-order Theory of Mind (ToM) is the cognitive capacity to attribute mental states about mental states, recursively. It is the psychological counterpart to the logical recursion in common knowledge.

• First-Order: 'Alice believes X.'
• Second-Order: 'Alice believes that Bob believes X.'
• Higher-Order (Nth-Order): Recursive embeddings beyond second order. Common knowledge requires an agent to effectively reason with an infinite-order Theory of Mind, as it involves 'I know that you know that I know...' ad infinitum. This is crucial for complex social reasoning, strategic games like chess, and understanding nuanced communication.

Recursive modeling is the computational implementation of higher-order Theory of Mind, where an agent explicitly constructs and reasons over models of other agents' models. An agent maintains a belief about the world, a model of what another agent believes about the world, a model of what the other agent believes the first agent believes, and so on.

• Mechanism: Creates a nested hierarchy of belief models.
• Challenge: The complexity grows exponentially with recursion depth. Common knowledge represents the limiting, idealized case of infinite recursion, which in practice is approximated to a sufficient depth for the task at hand, such as in competitive poker playing or diplomatic negotiation simulations.

Strategic reasoning is the process of making optimal decisions by explicitly modeling the likely decisions of other rational agents who are simultaneously modeling you. It is the practical application of recursive modeling in competitive or cooperative settings.

• Foundation: Relies on constructs like common knowledge and mutual belief. For example, the rationality of players in a game is often assumed to be common knowledge.
• Example - The Keynesian Beauty Contest: Participants must guess what the average guess will be, requiring reasoning about others' reasoning about others' reasoning. Equilibrium solutions depend heavily on the depth of strategic reasoning and shared knowledge assumptions.

Shared mental models are overlapping or aligned internal representations of a task, team, equipment, or situation held by members of a group. They enable coordinated, efficient action without the need for constant explicit communication.

• Relation to Common Knowledge: While a shared mental model implies some alignment of knowledge, it does not necessarily require the infinite recursive awareness of common knowledge. It is often a state of mutual belief or even just overlapping individual knowledge.
• Engineering Application: Critical in human-AI teaming, where ensuring an AI agent and a human operator have a shared model of the mission plan and environment state is key to effective collaboration and safety.