Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening

Mark Bedaywi, Scott Emmons, Nika Haghtalab, Stuart RussellarXiv 2026 · arXiv

TL;DR

This paper provides a polynomial-time algorithm to design near-optimal communication protocols for collaborative multi-agent systems without relying on restrictive structural assumptions. By introducing a novel "indistinguishable coarsening" technique based on graph regularity, the authors prove that a protocol's bit complexity can be independent of the observation space size, while demonstrating that an exponential dependence on the game's intrinsic communication complexity is computationally unavoidable.

What Problem Does This Paper Address?

In multi-agent systems—such as drone swarms coordinating maneuvers or a physician consulting an AI diagnostic model—agents hold distributed, correlated pieces of information. To make a high-utility decision, they must communicate. However, they face a three-way tension between maximizing decision utility, minimizing communication bandwidth (bit complexity), and minimizing computational overhead (finding the protocol in polynomial time).

Directly searching for a short, high-utility protocol is a combinatorially hard problem (NP-hard) because the space of candidate protocols grows exponentially with the observation space. Prior literature bypassed this hurdle by making restrictive structural assumptions (like "informational substitutes" or "weak learnability") or relying on Aumann agreement dynamics. This paper addresses the fundamental question: Among all communication protocols, when can we efficiently find one that is simultaneously short and useful without relying on narrow structural assumptions?

Methods

The authors introduce a novel framework called indistinguishable coarsening, driven by a powerful mathematical extension of graph theory: a Generalized Weighted Simultaneous Frieze-Kannan Regularity Lemma.

While standard weak regularity lemmas decompose a single unweighted matrix, this paper's generalized version simultaneously compresses a collection of reward matrices (one for each possible action) under an arbitrary joint probability distribution.

The core algorithm works as follows:

  1. Game Compression: It takes a communication game $G$ and constructs a compressed game $\hat{G}$ by partitioning the massive observation spaces of the agents into a constant number of subsets ($O(1/\epsilon^2)$).
  2. Energy Increment Argument: It iteratively refines these partitions using a martingale potential function. At each step, it uses an adapted version of the Alon-Naor algorithm to efficiently approximate the weighted "cut norm" (the rectangle with the largest absolute reward discrepancy) to find where the approximation is weakest.
  3. Protocol Execution: Because $\hat{G}$ is a genuine coarsening (a conditional expectation of the original rewards), the agents can simply communicate which coarse partition their true observation falls into. This ensures that the protocol's utility transfers back to the original game with zero approximation loss, successfully avoiding the "vicious cycle" where finer protocol tests blow up the required partition size.

Datasets

No empirical datasets or benchmarks were used for training or evaluation. This is a purely theoretical paper; its findings are validated through rigorous mathematical proofs, complexity analysis, and reductions to known hard problems (like graph coloring).

Key Insights and Ideas

  • Breaking the Vicious Cycle of Weak Regularity: Traditional indistinguishability arguments require finer approximations to remain robust against complex protocols, which explodes the number of bits needed. By forcing the compressed game to be a true coarsening, the authors ensure exact utility transfer for any protocol measurable within that coarsening.
  • The Fragility of Aumann Agreement: The paper reveals that standard agreement protocols (where agents repeatedly report best responses until they agree) are highly inefficient for utility aggregation. Agents can quickly agree on an action that is exponentially suboptimal. Furthermore, achieving lasting agreement (a state where the agreed action will never change again) can take $\Omega(n)$ rounds, requiring exponentially more bits than simply communicating the raw observations.
  • Unifying and Weakening Prior Assumptions: The authors prove that previous structural conditions like $w$-weak learnability actually imply that a game has a constant communication complexity ($CC_\alpha(G) = O(1)$). Therefore, designing a protocol based on low communication complexity is a strictly more general and permissive framework than past approaches.

Key Results

  • Algorithmic Upper Bound: For any achievable target utility $\alpha$ and error tolerance $\delta > 0$, the proposed algorithm runs in $\text{poly}(n, m, 1/\delta)$ time and produces a protocol achieving a utility of at least $\alpha - \delta$ using at most $O\left(\frac{2^{CC_\alpha(G)}\min\{m, 2^{CC_\alpha(G)}\}}{\delta^2}\right)$ bits, completely independent of the observation space size $n$.
  • Computational Lower Bound: The authors prove that unless $\text{P}=\text{NP}$, any polynomial-time algorithm attempting to find an optimal protocol must use at least $\approx 2^{CC(G)}$ bits in the worst case. This matches their algorithm's complexity up to a constant factor, proving the exponential blowup is unavoidable.
  • Agreement Suboptimality: They show that in low-complexity games, agents running an agreement protocol can be trapped in an agreement that yields no more than $2^{-CC(G)/2}$ utility.

Limitations and Future Work

  • Non-Adaptive Communication: The current protocol is non-adaptive; agents send their partition memberships simultaneously. The authors note that exploring whether adaptive, multi-round protocols can outperform this baseline is an open question.
  • One-Shot Setting: The model assumes a single round of information gathering and decision-making. Real-world AI agents often operate in stateful, sequential environments, motivating future extensions to Markov Decision Processes (MDPs).
  • Common-Interest Assumption: The framework assumes all agents share the exact same utility function. The authors suggest extending this to mixed-motive or strategic communication scenarios (e.g., bridging this work with Bayesian persuasion models).

Summary updated

Abstract

Our results show that the existence of a short high-utility protocol already suffices for efficient communication. In particular, in a game with $n$ possible observations and $m$ actions: (1) For any achievable target utility $α$, we give an algorithm with $\mathrm{poly}(n, m, 1/ε)$ runtime that designs a protocol achieving utility at least $α-ε$ using only $2^{\mathcal O(CC_α(G))}/ε^2$ bits of communication. Here, $CC_α(G)$ is the minimum number of bits used by any protocol, even a computationally inefficient one, to achieve utility $α$. (2) We prove that this exponential dependence on $CC_α(G)$ is tight up to a constant. That is, unless $\mathrm P=\mathrm{NP}$, no polynomial-time algorithm can in general find optimal protocols using fewer than $2^{CC_α(G) -2}$ bits. We note that our results strictly weaken the assumptions required by prior work in the multi-agent information aggregation literature, filling a gap that had remained elusive even for games with constant $CC_α(G)$. In particular, prior guarantees for agreement-based information aggregation rely on structural assumptions such as informational substitutes or weak learnability. We show that these assumptions already imply $CC_α(G) = O(1)$ and are therefore more restrictive conditions than required by our protocol to succeed. On a technical level, our results involve a novel strengthening of the Frieze-Kannan weak regularity lemma and yield the following powerful polynomial-time transformation tool: for every communication game $G$, it constructs a game $\hat G$ that is a coarsening of the agents' observation spaces into constant-size partitions, such that $G$ and $\hat G$ are indistinguishable with respect to every short communication protocol. This coarsening theorem is the engine behind our algorithm and may be of independent interest.
BibTeX
@misc{bedaywi2026computationally,
  author = {Mark Bedaywi and Scott Emmons and Nika Haghtalab and Stuart Russell},
  title = {{Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening}},
  year = {2026},
  eprint = {2608.05327},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.05327},
}
Figure