# Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria

arXiv: https://arxiv.org/abs/2609.22757 · HTML: https://mlsanity.com/paper/2609.22757/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 78 references that are in the map.
- First posted on arXiv 19 Sep 2026.

## Builds on (most cited first, 30 of 40)

- [Algorithmic Collusion by Large Language Models](https://mlsanity.com/paper/2404.00806/) (2024)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Algorithmic Bayesian Persuasion](https://mlsanity.com/paper/1503.05988/) (2015)
- [Mechanisms for a No-Regret Agent: Beyond the Common Prior](https://mlsanity.com/paper/2009.05518/) (2020)
- [Inapproximability of Nash Equilibrium](https://mlsanity.com/paper/1405.3322/) (2014)
- [The Complexity of Gradient Descent: CLS = PPAD cap PLS](https://mlsanity.com/paper/2011.01929/) (2020)
- [Complexity-Theoretic Implications of Multicalibration](https://mlsanity.com/paper/2312.17223/) (2023)
- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [High dimensional online calibration in polynomial time](https://mlsanity.com/paper/2504.09096/) (2025)
- [High-Dimensional Calibration from Swap Regret](https://mlsanity.com/paper/2505.21460/) (2025)
- [On preserving non-discrimination when combining expert advice](https://mlsanity.com/paper/1810.11829/) (2018)
- [Efficient Prior-Free Mechanisms for No-Regret Agents](https://mlsanity.com/paper/2311.07754/) (2023)
- [Regulation of Algorithmic Collusion](https://mlsanity.com/paper/2401.15794/) (2024)
- [Regulation of Algorithmic Collusion, Refined: Testing Pessimistic Calibrated Regret](https://mlsanity.com/paper/2501.09740/) (2025)
- [Pure-Circuit: Tight Inapproximability for PPAD](https://mlsanity.com/paper/2209.15149/) (2022)
- [Algorithmic Collusion Without Threats](https://mlsanity.com/paper/2409.03956/) (2024)
- [Query Complexity of Approximate Nash Equilibria](https://mlsanity.com/paper/1306.6686/) (2013)
- [Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria](https://mlsanity.com/paper/1805.06387/) (2018)
- [Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games](https://mlsanity.com/paper/2203.12074/) (2022)
- [The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points](https://mlsanity.com/paper/2207.07557/) (2022)
- [On the Communication Complexity of Approximate Nash Equilibria](https://mlsanity.com/paper/1302.3793/) (2013)
- [The Query Complexity of Correlated Equilibria](https://mlsanity.com/paper/1305.4874/) (2013)
- [Competitive Information Design for Pandora's Box](https://mlsanity.com/paper/2103.03769/) (2021)
- [Online Optimization Algorithms in Repeated Price Competition: Equilibrium Learning and Algorithmic Collusion](https://mlsanity.com/paper/2412.15707/) (2024)
- [Information Design With Large Language Models](https://mlsanity.com/paper/2509.25565/) (2025)
- [Constant Rank Bimatrix Games are PPAD-hard](https://mlsanity.com/paper/1402.3350/) (2014)
- [Unique End of Potential Line](https://mlsanity.com/paper/1811.03841/) (2018)
- [Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria](https://mlsanity.com/paper/1909.03210/) (2019)

## Built on by (most cited first, 1 of 1)

- [Normal-Form Correlation in Markov Games](https://mlsanity.com/paper/2610.03621/) (2026)

## Abstract (arXiv)

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 CLS = PPAD cap 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.