Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.22757 · 1 citation · 78 references
Computer Science

TL;DR

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, is examined, showing that it is at least as hard as the P-matrix linear complementarity problem, and hence as hard as simple stochastic games.

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.

View source

Similar papers

#machine learning Preprint Oct 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 R...

I. Anagnostides, Constantinos Daskalakis, Gabriele Farina et al. · 1 citation
#machine learning Preprint Sep 2026

Constant regret in general games via higher-order optimism

We introduce an uncoupled learning algorithm which, when employed by all players of an arbitrary $N$-player normal form game with up to $K$ actions per player, guarantees $O(N^3\log^2 K)$ individual regret, uniformly over the horizon of play. The proposed algorithm - which we call higher-order optimism with discounting...

Omar Abbadi, R. Laraki, P. Mertikopoulos · 4 citations · ⚡4
Preprint Aug 2026

What preferences can - and cannot - predict in multi-agent online learning

A three-player game is constructed with a preferentially stable set whose span is dynamically unstable, showing that preferences do not suffice as a criterion of dynamic stability and bridges the gap via the notion of resilience under aggregate deviations.

Omar Abbadi, R. Laraki, P. Mertikopoulos · 2 citations
Preprint Aug 2026

Learning under Opponent Unawareness in Linear-Quadratic Stochastic Games

This paper studies learning in infinite-horizon, nonzero-sum linear-quadratic stochastic games under a radically uncoupled information structure, where players are either unaware of opponents or strategically oblivious, observing only their own action history.

Dantong Chu, Xue-Feng Gao, Yufei Zhang · 0 citations
Open access Sep 2026

The Complexity of Subgame-perfect Equilibria in Parity and Mean-payoff Games

In this paper, we prove that the SPE constrained existence problem, i.e. the problem of deciding, in a given game, the existence of a subgame-perfect equilibrium that generates a payoff profile between two given thresholds, is \(\mathsf {NP} \) -complete for both parity games and mean-payoff games. For that purpose, we...

Léonard Brice, J. Raskin, Marie van den Bogaard · 0 citations
Preprint Aug 2026

Best Response Dynamics for Zero-Sum Dynamic Games with Partial-Asymmetric Information

Numerical results reveal that the game's value converges after only a few iterations, suggesting that higher-order belief states provide vanishing benefit, and an alternative approach based on best response dynamics is proposed, which provides insights into belief representation and theory of mind challenges.

Yuxiang Guan, Iman Shames, Tyler H. Summers · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.