The Common Information Approach to Decentralized Coordination

48 concepts32 papers1 proposal

Decentralized control and multi-agent planning problems (such as Dec-POMDPs) are notoriously difficult to solve. When multiple autonomous agents must cooperate in a stochastic environment based on asymmetric, local observations, they face a fundamental computational barrier: the nightmare of nested beliefs.

To choose an optimal action, Agent A must guess what Agent B observed. However, Agent B's action depends on what Agent B thinks Agent A observed, which in turn depends on what Agent A thinks Agent B thinks Agent A observed. As noted by Adam P. Vogel et al. in Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs, this infinite regress of "I think that you think that I think" makes exact decentralized decision-making computationally intractable (NEXP-complete).

The common information approach is a powerful mathematical framework that breaks this infinite loop. It proves that decentralized coordination problems can be systematically transformed into equivalent, centralized planning problems, allowing researchers to apply standard single-agent optimization tools to multi-agent systems.

Splitting the Information Structure

The core insight behind this framework is that even when agents have different private data, they almost always share a significant amount of history. In a foundational paper, Aditya Mahajan, Ashutosh Nayyar, and Demosthenis Teneketzis formalised this by partitioning each agent's history into two distinct components in Decentralized Stochastic Control with Partial History Sharing: A Common Information Approach:

  1. Common Information: Data known to all agents in the system (such as past public actions, shared observations, or delayed control signals).
  2. Private Information: Local observations known exclusively to an individual agent.

By separating these layers, we can analyze the system through the eyes of a fictitious, centralized virtual coordinator who only observes the common information.

Prescriptions Instead of Commands

How can a coordinator who cannot see private data guide decentralized agents effectively? The coordinator cannot issue direct action commands (e.g., telling an agent to "move left"), because it doesn't know the agent's exact local state.

Instead, the coordinator issues prescriptions (or decision rules). A prescription is a mathematical function that maps an agent's private information to a specific action. For instance, the coordinator might issue a rule stating: "If your local sensor reads high, turn left; if it reads low, turn right."

[ Common Information History ]
              │
              ▼
    ┌───────────────────┐
    │Virtual Coordinator│
    └─────────┬─────────┘
              │
              ▼ (Generates Prescriptions)
    ┌───────────────────┐
    │    Prescription   │ ──► (Maps Private Data to Actions)
    └───────────────────┐
              │
              ▼
    ┌───────────────────┐
    │ Decentralized Act │
    └───────────────────┘

As explained by Aditya Mahajan and Jalal Arabneydi in Reinforcement learning in decentralized stochastic control systems with partial history sharing, this mechanism shifts the perspective from individual agent reactions to a unified planning problem. Because the common information is public, every agent can independently compute the exact same common information state and deduce the optimal prescriptions. They then evaluate these shared prescriptions using their local private data, executing perfectly synchronized actions without needing real-time communication.

Why It Works: The Decentralized-to-Centralized Reduction

The magic of this approach lies in how it transforms the underlying state space. Instead of tracking individual histories, the virtual coordinator tracks a common information belief (or public belief space)—a posterior probability distribution over the global system states and agents' private data, conditioned on the shared common history.

This belief serves as a sufficient statistic for the entire system history. As demonstrated by Jilles Steeve Dibangoye et al. in Optimally Solving Dec-POMDPs as Continuous-State MDPs, when we treat this joint distribution (known as the occupancy state) as the state of a new system, the transitions become completely deterministic.

The subsequent distribution over histories is uniquely determined by the current distribution and the chosen prescriptions. This reduction converts a stochastic, partially observable decentralized problem into a continuous-state, deterministic single-agent MDP. This equivalence allows researchers to bypass nested beliefs entirely and apply standard centralized tools like dynamic programming, heuristic search (Scaling Up Decentralized MDPs Through Heuristic Search), or value iteration (Point Based Value Iteration with Optimal Belief Compression for Dec-POMDPs).

Applications Across Multi-Agent Domains

The common information framework has been successfully adapted across several distinct research directions:

Key Foundational Work

Language Learning in Multi-Agent Systems (2005) — contributed 1 concept elements to this direction.
Reasoning about joint beliefs for execution-time communication decisions (2005) — contributed 1 concept elements to this direction.
The Complexity of Decentralized Control of Markov Decision Processes (2000) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_common_information_coordination_265dadfe,
  title = {common information coordination},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/common-information-coordination/rdr_265dadfe8e0b4603ad3bc924014fd479},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_common_information_coordination_265dadfe_v1,
  title = {common information coordination},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/common-information-coordination/rdr_265dadfe8e0b4603ad3bc924014fd479/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake