CS Paper Radar

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

Ioannis Anagnostides, Weiqiang Zheng

cs.GT cs.CCcs.DScs.LG ·submitted 2026-09-19 04:38 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Normal-Form Correlation in Markov Games

cs.GT cs.CCcs.DScs.LG ·2026-10-02 ·Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm +1 more
similarity 0.71
Abstract

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 $n$. In particular, with $S$ states, horizon $H$, and at most $A$ actions per player, it computes an $ε$-NFCE in time $S(AH/ε)^{O(n)}$. This is the first algorithm polynomial in $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.

0.43

Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games

cs.GT cs.AIcs.MAecon.TH ·2026-11-04 ·Sam Ganzfried
similarity 0.69
Abstract

We give a deterministic polynomial-time algorithm for computing an exact extensive-form proper equilibrium in a finite two-player zero-sum extensive-form game with perfect recall and rational data. Properness is understood in the agent normal form: an action at an information set is penalized relative to a better action while all other local behavioral choices, including the player's own future actions, remain fixed. Our algorithm assigns each information set a geometric permutahedron of allowable action probabilities. A scaled doubly stochastic representation embeds these restrictions in a polynomial-size sequence-form polytope; a saddle point then satisfies the local $\varepsilon$-properness inequalities. To obtain an exact equilibrium rather than a solution at an arbitrarily small numerical perturbation, we establish sign stability of a parametric linear system, construct a persistent feasible basis, and extract the limits of behavioral ratios. The resulting probabilities are rational and have polynomial encoding length, including at information sets whose realization probabilities vanish.

0.25

Planning Against Learning in Rank-1 Games

cs.GT ·2026-08-18 ·William Overman
similarity 0.69
Abstract

Learning algorithms are often used to make decisions in repeated multi-agent environments. When another player understands how a learner adapts from past experience, that player can plan strategically across rounds to influence the learner's future behavior. Recent work shows that optimizing against Replicator Dynamics, the continuous-time analogue of Multiplicative Weights Update, is tractable in zero-sum games but can be hard in unrestricted general-sum games. We study the first structured class beyond zero sum: bimatrix games satisfying $\text{rank}(A+B)=1$, for which Nash equilibria can be computed in polynomial time. Our main result shows that this equilibrium tractability does not extend to planning against learning dynamics. Unless $\mathsf{P}=\mathsf{NP}$, approximating the optimizer's optimal continuous-time reward within a fixed additive constant is NP-hard even when $\text{rank}(A+B)=1$, the learner starts from the uniform state, and the optimizer is restricted to constant strategies. The hardness persists for bounded payoff matrices and polynomially bounded horizons. We complement this result with structural characterizations of several tractable special cases. Thus rank-one games already separate efficient equilibrium computation from strategic planning against a learning opponent.

0.06

How Learning Selects Equilibria and When It Leads to Collusion

cs.GT ·2026-10-26 ·Hanzhang Wang, Manxi Wu
benchmark similarity 0.69
Abstract

We study how learning algorithm design shapes equilibrium selection in infinite-horizon discounted Markov games with finite states and actions. Each episode, players choose smooth best responses to beliefs about opponents' policies, test them using noisy observations, and resample rejected beliefs or explore at rates determined by increasing transformations of their discounted values. We show that stochastically stable states induce approximate stationary Nash equilibria maximizing the minimum transformed discounted value across players, with transformations governing which players selection favors. In repeated games with bounded recall of noisy public signals, longer recall weakly increases the selected minimum transformed value. In repeated Cournot games, every stochastically stable state induces an approximate public perfect equilibrium whose minimum discounted profit across firms exceeds the Cournot-Nash benchmark. Collusion is therefore inevitable under these conditions and learning dynamics. For symmetric firms, selected profits can approach the monopoly benchmark arbitrarily closely. These results offer a novel equilibrium-selection perspective on algorithmic collusion.

0.17

The Complexity of Multiplayer Colonel Blotto Games with Player-Specific Values

cs.GT cs.CCecon.TH ·2026-09-24 ·Martin Bichler, Abheek Ghosh
similarity 0.68
Abstract · 64 pages, 3 figures

We study equilibrium computation in discrete multiplayer Colonel Blotto games with player-specific battlefield values. In the two-player model with common battlefield values, equilibria can be computed in polynomial time. We show that this tractability breaks down in the multiplayer model with player-specific values under the standard uniform tie-breaking rule. In particular, computing a $(c/n)$-approximate Nash equilibrium is PPAD-hard for some constant $c>0$, even when every player has three resources, where $n$ is the number of players. The main technical step is PPAD-hardness for computing a constant-approximate well-supported Nash equilibrium. In contrast, under uniform tie-breaking, a pure Nash equilibrium can be computed in polynomial time when every player has one resource. We also prove PPAD membership for computing $\varepsilon$-approximate Nash equilibria for inverse-exponentially small $\varepsilon$. Finally, for non-uniform monotone tie-breaking, we show PPAD-hardness even when every player has one resource and all players have identical battlefield values.

0.25

Bayesian Replicator Dynamics and the Inversion of Strict Dominance in Bimatrix Games

cs.GT cs.MA ·2026-10-26 ·Jaime Ruiz-Serra, Nihat Ay, Michael Harré
similarity 0.68
Abstract · 18 pages, 3 figures

Replicator dynamics, the central model of evolutionary game theory, describe populations evolving under selection and agents learning by trial and error. They also admit a third use: continuous-time Bayesian inference, in which an agent planning against an opponent accumulates evidence for each candidate strategy. Here we show that this use divides all two-player games into two classes. With the standard expected-utility payoff, the dynamics can be expressed as Bayesian updating only in games (with any number of actions) where no player has a dominant strategy. The logarithmic payoff of Ay and Erb (2005) admits the Bayesian representation in every game. Coordination, anti-coordination, and cyclic games share qualitative dynamics under both payoff definitions, with equilibria displaced and selection thresholds shifted. In contrast, the flows of every game with a dominant strategy are reversed between the payoff definitions, with the strictly dominant strategy eliminated under logarithmic payoffs. Cooperation therefore emerges in the Prisoner's Dilemma, and games of common interest converge to mutual defection. For two-action games the classification is complete and rests on an exact Hamiltonian structure shared by both payoff definitions. The structure gives a behavioural test: cycles in the classic Matching Pennies game have amplitude-independent period (isochronous) under logarithmic payoffs, but not under expected utility. Logarithmic evidence integration thus determines which strategic outcomes dynamical selection can reach, wherever learning approximates Bayesian updating.

0.23

Learning and Steering in Incomplete-Information Games

cs.GT cs.AIcs.LGeess.SY+1 ·2026-11-05 ·Asrın Efe Yorulmaz, Tamer Başar
similarity 0.68
Abstract · 57 pages, 5 figures

In many modern multi-agent systems, a mediator seeks to influence strategic decision dynamics using only outcome-level feedback and without knowing agents' utilities. In this work, we study how a mediator can learn an unknown game and steer adaptive agents toward outcomes that maximize her utility using only trajectory feedback. The mediator knows the game form and her own objective, but not the agents' utilities. Moreover, she commits to nonnegative payments and provides recommendations and contexts, but receives only a single realized terminal outcome rather than full-information feedback. We develop halving-type algorithms that learn utility differences in normal-form games and conditional continuation-value differences in extensive-form games, achieving a sample complexity of $\widetilde O(\varepsilon^{-2})$ that matches worst-case lower bounds up to logarithmic factors. We then combine these learning procedures with a Lagrangian formulation in an online Learn-Compute-Steer algorithm that interleaves learning, equilibrium computation, and steering toward mediator-optimal extensive-form correlated equilibria (EFCE). With high probability, the Learn-Compute-Steer algorithm achieves a directness gap and an optimality gap of $\widetilde O(T^{-1/4})$, while time-average payments are of $\widetilde O(T^{-1/8})$.

0.23

The Complexity of Exact and Approximate Nash Equilibria in Anonymous Games

cs.GT ·2026-10-12 ·Zhengyang Liu
theory similarity 0.67
Abstract · 48 pages, including appendices and references; 2 figures and 4 tables

We prove that, for every fixed rational $c>0$, computing a $2^{-n^c}$-approximate Nash equilibrium in an $n$-player two-strategy anonymous game is $\mathsf{PPAD}$-complete. This holds even when one strategy always pays $1/2$ and, for all but two players, the other is constant outside at most five opponent counts. The reduction uses coefficient estimates to simulate circuit constraints approximately. Exact computation requires eliminating the simulation error: with three strategies, a separate construction uses polynomial roots to implement circuit gates exactly. This yields $\mathsf{FIXP}$-completeness of exact equilibrium computation under separable-linear reductions and $\mathsf{FIXP}_a$-completeness of approximation in distance to an exact equilibrium.

0.15