Metraipolis › archive › dc_12c1fef309bd
Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening — arXiv:2608.05327
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.05327
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-26T20:01:42.132Z
- SHA-256 of the archived text
8ebbeff2f6d4fef3e9c7091c3cd07f88975107a21dec00a1629e8d12e20816a2- Stable URL of this page
https://metraipolis.com/documento/dc_12c1fef309bd
How to cite
Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening — arXiv:2608.05327 — arXiv (en), https://arxiv.org/abs/2608.05327 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_12c1fef309bd (Metraipolis archive dc_12c1fef309bd, sha256 8ebbeff2f6d4fef3e9c7091c3cd07f88975107a21dec00a1629e8d12e20816a2)
BibTeX
@misc{dc12c1fef309bd,
title = {Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening — arXiv:2608.05327},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.05327},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_12c1fef309bd; sha256 8ebbeff2f6d4fef3e9c7091c3cd07f88975107a21dec00a1629e8d12e20816a2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.05327. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\alpha$, we give an algorithm with $\mathrm{poly}(n, m, 1/\epsilon)$ runtime that designs a protocol achieving utility at least $\alpha-\epsilon$ using only $2^{\mathcal O(CC_\alpha(G))}/\epsilon^2$ bits of communication. Here, $CC_\alpha(G)$ is the minimum number of bits used by any protocol, even a computationally inefficient one, to achieve utility $\alpha$. (2) We prove that this exponential dependence on $CC_\alpha(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_\alpha(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_\alpha(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_\alpha(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.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-07 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2608.05327 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-26T19:47:33.599Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).