Metraipolis › archive › dc_7574484ffd48
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria — arXiv:2609.22757
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.22757
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:58:02.533Z
- SHA-256 of the archived text
c9f873806c4ba28b380792be84f194b1bfed8e10e0d900061a7cb72b08b719df- Stable URL of this page
https://metraipolis.com/documento/dc_7574484ffd48
How to cite
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria — arXiv:2609.22757 — arXiv (en), https://arxiv.org/abs/2609.22757 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7574484ffd48 (Metraipolis archive dc_7574484ffd48, sha256 c9f873806c4ba28b380792be84f194b1bfed8e10e0d900061a7cb72b08b719df)
BibTeX
@misc{dc7574484ffd48,
title = {Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria — arXiv:2609.22757},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.22757},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7574484ffd48; sha256 c9f873806c4ba28b380792be84f194b1bfed8e10e0d900061a7cb72b08b719df},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.22757. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A (coarse) correlated equilibrium (CE) is information-value-free (IVF) if a player can match the payoff obtained from recommendations by committing to a fixed action. Motivated by the problem of regulating algorithmic collusion, this refinement was introduced by Hartline, Wang, and Zhang [EC'26], who showed that it can be computed in polynomial time in explicitly represented normal-form game. In this paper, we examine the complexity of IVF(C)CEs in succinct games, which model more realistic strategic interactions that feature either many players or exponentially many pure strategies. We first show that computing an information-value-free CE is PPAD-complete in many-player polymatrix games or two-player Bayesian games, even when the approximation is a constant. We also prove an unconditional exponential query lower bound. Our results establish that IVFCEs are intractable, even in the centralized model, and rule out the existence of any efficient learning dynamics. This significantly strengthens the impossibility result of Hartline, Wang, and Zhang, which concerns a particular class of learning algorithms, and furnishes strong computational critiques of recent regulation on algorithmic collusion. To sidestep these hardness results, we examine the complexity of information-value-free CCE. Certain no-regret algorithms---such as regret matching or FTRL---provide a fully polynomial-time approximation scheme (FPTAS) for this problem. The complexity when the approximation is exponentially small turns out to be nuanced. On the one hand, leveraging no-regret dynamics, we establish membership in $\text{CLS} = \text{PPAD} \cap \text{PLS}$. On the other hand, we show that it is at least as hard as the P-matrix linear complementarity problem, and hence as hard as simple stochastic games. This shows that even IVFCCEs are unlikely to admit a polynomial-time algorithm barring a major breakthrough.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-22 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.22757 — 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-09T06:52:12.753Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).