cs.GTSep 19, 2026

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

Authors: Ioannis Anagnostides, Weiqiang Zheng

Organizations: Carnegie Mellon University · Yale University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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 CLS=PPAD∩PLS\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.

Figures & tables

EquilibriumExplicit normal formSuccinct normal form
NEPPAD\mathsf{PPAD} -complete for 1/poly⁡1/\operatorname{poly} approximation [ Chen et al., 2009 ]PPAD\mathsf{PPAD} -complete for constant approximation [ Rubinstein, 2015 ]
CE  
CCEP\mathsf{P} [ Aumann, 1987 ]P\mathsf{P} [ Papadimitriou and Roughgarden, 2008 ]
IVFCEP\mathsf{P} [ Hartline et al., 2026 ]PPAD\mathsf{PPAD} -complete for constant approximation
IVFCCEP\mathsf{P} [ Hartline et al., 2026 ]FPTAS CLS\mathsf{CLS} membership PP -LCP-hard
Table 1: Computational complexity of equilibrium notions in normal-form games: Nash equilibrium (NE), correlated equilibrium (CE), coarse correlated equilibrium (CCE), information-value-free CE (IVFCE), and information-value-free CCE (IVFCCE). The results of this paper are highlighted in the shaded cells.
More in this topic

Game Theory

Game theory studies how interacting decision-makers choose strategies, form agreements, and shape outcomes under competition and cooperation.

See all 233 papers

Explore similar work

CardsList
Oct 2, 2026

Normal-Form Correlation in Markov Games

There has been a surge of recent work on correlated equilibrium concepts in Markov games. However, existing results focus on concepts weaker than normal-form correlated equilibria (NFCEs), leaving open the more challenging question of computing such equilibria, which goes back to the seminal work of Papadimitriou and Roughgarden (JACM'08). Here, we establish the first efficient algorithm for NFCEs in finite-horizon Markov games with a fixed number of players nn. In particular, with SS states, horizon HH, and at most AA actions per player, it computes an εε-NFCE in time S(AH/ε)O(n)S(AH/ε)^{O(n)}. This is the first algorithm polynomial in 1/ε1/ε and the description of the game for NFCEs in an interesting class of problems beyond the normal-form setting. Moreover, under the usual assumption that recommendations are independent across states, we show PPAD-completeness---that is, computational equivalence to Nash equilibria---either in many-player games or when the precision is exponentially small. The key idea behind our approach is to run backward induction on a sequence of auxiliary stage games, but with the twist that in each step we compute a constant-expectation correlated equilibrium. This is a natural refinement of correlated equilibrium in which the conditional expected payoff from obeying is independent of the recommendation. In fact, our reduction goes both ways, establishing an equivalence between constant-expectation CEs and NFCEs in Markov games. For a fixed number of players, we observe that a constant-expectation CE can be computed approximately by combining linear programming with suitable discretization. In contrast, it is PPAD-hard in i) polymatrix (many-player) games at constant precision, and ii) two-player games at exponentially small precision. The latter result follows from an unexpected connection to rank-2 two-player games.

Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina +3

Carnegie Mellon University · Massachusetts Institute of Technology · University of Texas at Austin +1

Game Theory
AskPDF
Feb 19, 2026

Algorithmic Collusion at Test Time: A Meta-game Design and Evaluation

The threat of algorithmic collusion, and whether it merits regulatory intervention, remains debated, as existing evaluations of its emergence often rely on long learning horizons, assumptions about counterparty rationality in adopting collusive strategies, and symmetry in hyperparameters and economic settings among players. To study collusion risk, we introduce a meta-game design for analyzing algorithmic behavior under test-time constraints. We model agents as possessing pretrained policies with distinct strategic characteristics (e.g., competitive, naively cooperative, or robustly collusive), and formulate the problem as selecting a meta-strategy that combines a pretrained, initial policy with an in-game adaptation rule. We seek to examine whether collusion can emerge under rational choices and how agents co-adapt toward cooperation or competition. To this end, we sample normal-form empirical games over meta-strategy profiles, compute relevant game statistics (e.g., payoffs against individuals and regret against an equilibrium mixture of opponents), and construct empirical best-response graphs to uncover strategic relationships. We evaluate reinforcement-learning, UCB, and LLM-based strategies in repeated pricing games under symmetric and asymmetric cost settings, and present findings on the feasibility of algorithmic collusion and the effectiveness of pricing strategies in practical ``test-time'' environments. The source code is available at: https://github.com/chailab-rutgers/CollusionMetagame.

Yuhong Luo, Daniel Schoepflin, Xintong Wang

Rutgers University · DIMACS, Rutgers University

Algorithmic CollusionGame TheoryRepeated Games
AskPDF
Oct 20, 2026

Fixed Sets and the Hardness of Computing Correlated Equilibria

We show that computing an approximate correlated equilibrium of a polytope game is PPAD-complete, and thus polynomial-time equivalent to finding a Nash equilibrium. This challenges the conventional view in game theory that correlated equilibria are more tractable objects than Nash equilibria. From a conceptual standpoint, we connect correlated equilibria to a natural generalization of fixed points, which we call fixed sets. A fixed set of a continuous function ff is a nonempty finite set SS such that S⊆conv⁡f(S)S \subseteq \operatorname{conv} f(S). Our main technical contribution is to prove that computing a fixed set is PPAD-hard even at inverse polynomial precision.

Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina +3

Carnegie Mellon University. · Massachusetts Institute of Technology. · University of Texas, Austin. +1

Game Theory
AskPDF