Shared Randomness for Decentralized Coordination

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 241 papers60 conceptsfrozen 2026-10-04

In decentralized systems, multiple agents must often act in unison to achieve a common goal. However, when agents cannot communicate in real-time, they face a fundamental "coordination gap." If each agent makes decisions based on independent randomness, they risk collisions, redundant exploration, and suboptimal equilibria.

The research direction explored across these papers identifies a powerful solution: shared randomness. By providing agents with a common random seed or a "correlation device," researchers have shown that decentralized agents can achieve the performance of centralized controllers with minimal or zero communication overhead.

The Virtual Wire: Why Shared Seeds Work

The core intuition behind shared randomness is that it acts as a "virtual wire" between agents. In a standard Decentralized Partially Observable Markov Decision Process (Dec-POMDP), agents are often limited by their local observations. Daniel S. Bernstein, Eric A. Hansen, and Shlomo Zilberstein demonstrated in Bounded Policy Iteration for Decentralized POMDPs that a "correlation device"—a shared signal—allows agents to synchronize their stochastic finite-state controllers.

This works because a shared random seed allows two independent programs to generate the exact same sequence of pseudo-random numbers. If Agent A and Agent B agree on a seed, they can both "roll the same die" at every time step. This allows them to:

  1. Synchronize Mode Selection: In multi-modal policies where several optimal actions exist, agents can use the shared seed to pick the same "mode" without talking. Junjie Sheng and colleagues use this in Negotiated Reasoning: On Provably Addressing Relative Over-Generalization to ensure agents converge on the same high-reward strategy.
  2. Partition Tasks: In distributed computing, as noted by Adam Karczmarz in Distributed Tasks: Introducing Distributed Computing to Programming Competitions, nodes can use a shared seed to independently decide which part of a dataset to process, ensuring no two nodes do the same work.

Expanding the Equilibrium Space

In game theory, the "Nash Equilibrium" is the standard solution where no player wants to deviate. However, Nash equilibria are often suboptimal compared to what a central coordinator could achieve. By introducing shared randomness, the goal shifts toward a Correlated Equilibrium.

William Brown shows in Learning in Multi-Player Stochastic Games that a shared random signal allows independent learners to achieve no-regret bounds and converge to these superior correlated equilibria. Similarly, Chi Jin and co-authors utilize shared seeds in V-Learning - A Simple, Efficient, Decentralized Algorithm for Multiagent RL to implement correlated equilibria with linear sample complexity, bypassing the "curse of multiagents."

This concept reaches its theoretical limit in "program games," where agents simulate each other's source code. Caspar Oesterheld, Emery Cooper, and Vincent Conitzer prove in Characterising Simulation-Based Program Equilibria that access to shared randomness allows agents to satisfy a "folk theorem"—meaning they can sustain any mutually beneficial outcome as a stable equilibrium by synchronizing their internal simulations and punishment strategies.

Collision Avoidance Without Communication

One of the most practical applications of this idea is in Multi-Armed Bandit (MAB) problems. When multiple agents pull arms in a bandit, they usually "collide" if they pick the same arm, receiving no reward.

Sebastien Bubeck and Mark Sellke have published a series of papers, including Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions, demonstrating that shared randomness allows agents to partition the "arm space" using tree-based strategies. By using a common external reference, agents can perturb their decision boundaries such that even if their local reward estimates are slightly different, they are highly unlikely to select the same arm.

This synchronization extends to the timing of learning. In Decentralized Learning in Online Queuing Systems, Flore Sentenac and colleagues use shared seeds to coordinate exploration and exploitation phases. This ensures that agents aren't all exploring (and potentially crashing the system) at the same time.

Zero-Shot Coordination and Tie-Breaking

A major hurdle in AI is "Zero-Shot Coordination" (ZSC)—coordinating with a novel partner at test time. If two agents are trained independently to play a game like Hanabi, they might develop different "conventions."

Johannes Treutlein and Jakob Nicolaus Foerster argue in A New Formalism, Method and Open Issues for Zero-Shot Coordination that shared deterministic functions (like a hash of the game state) act as a form of shared randomness that helps break ties. By agreeing on a way to rank strategies, agents can converge on the same convention without prior agreement.

Beyond Coordination: Privacy and Resilience

The utility of shared randomness extends into privacy and system resilience:

In summary, shared randomness transforms a collection of independent actors into a cohesive unit. By providing a common frame of reference, it allows agents to simulate the benefits of communication and centralization where neither is actually possible.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 59 papers
  2. Version 1 · 2026-10-04 · 41 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_shared_randomness_synchronization_4295743f,
  title = {shared randomness synchronization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shared-randomness-synchronization/rdr_4295743f2f264df7a4e2b18c2276bd11},
  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_shared_randomness_for_decentralized_coor_4295743f_v1,
  title = {Shared Randomness for Decentralized Coordination},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shared-randomness-for-decentralized-coordination/rdr_4295743f2f264df7a4e2b18c2276bd11/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}