Summary
Algorithmic collusion occurs when computer programs in competitive settings implicitly cooperate to keep prices high or restrict competition. The authors study a refined notion called information-value-free equilibria, which helps understand when players can benefit from following signals or recommendations. They show that finding these equilibria is very hard computationally in realistic, large strategic settings, which implies that many simple methods for detecting or regulating algorithmic collusion will not scale well. However, some related equilibrium concepts remain tractable with known learning algorithms, but only under certain approximations.
What this means in practice
- •For antitrust regulators: Design monitoring tools that account for the computational limits of detecting collusion in complex markets to avoid relying on infeasible equilibrium computations.
- •For algorithmic trading teams: Inform design of automated strategies by understanding which equilibria are computationally tractable and which are not, guiding realistic assumptions about competitor behavior.
A theory result. No direct application yet.
Abstract
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.