CS Paper Radar

The Complexity of Nash Equilibrium in Network Congestion and Coordination Games

Ioannis Anagnostides, Ioannis Panageas, Jingming Yan

cs.GT cs.CC ·submitted 2026-09-27 05:06 UTC · v1

Abstract

We show that computing a Nash equilibrium is CLS-complete for linear network congestion and network coordination games. As a result, finding a KKT point of a bilinear polynomial is CLS-complete.

Closest papers

Nearest neighbours by meaning across the whole index.

On Existence and Computational Complexity of Quasi-strict Equilibria

cs.GT ·2026-11-04 ·Kristoffer Arnsfelt Hansen, Xinhao Nie
similarity 0.65
Abstract

Quasi-strict Nash equilibrium, introduced by Harsanyi in 1973, is the Nash equilibrium refinement that requires every pure best response to be played with positive probability. Norde established that any bimatrix game admits a quasi-strict Nash equilibrium. We give a substantially simpler proof of this result that in particular avoids an intricate limit argument used in the final step of the proof by Norde. Our existence proof allows us to positively resolve the outstanding open question of PPAD membership of the problem of computing a quasi-strict Nash equilibrium, thereby settling its precise complexity. In games with three or more players, a quasi-strict Nash equilibrium is not guaranteed to exist, leading to the natural problem of deciding the existence of a quasi-strict Nash equilibrium in a given strategic form game. We show that this problem is $\exists\mathbb{R}$-complete, strengthening a previous NP-hardness result.

0.07

The Complexity of Computing Nash Equilibria in Colonel Blotto Games

cs.GT cs.CC ·2026-10-05 ·Vasilis Pollatos, Andreas Kontogiannis
theory similarity 0.64
Abstract

We study the complexity of Nash equilibrium computation in discrete Colonel Blotto games. For two-player general-sum Colonel Blotto with monotonic piecewise-constant battlefield payoffs, we show that computing an inverse-polynomial approximate Nash equilibrium is PPAD-hard, even with only two battlefields and a constant number of pieces per battlefield, thereby resolving an open question of [KPF+25]. Allowing more battlefields, the hardness persists when every battlefield payoff is $2$-piecewise constant with respect to either player's allocation. A general PPAD-membership theorem for multiplayer Blotto with arbitrary local reward functions then implies PPAD-completeness for both hardness results. Motivated by fixed-rank bimatrix games, we then identify a tractable frontier within two-player general-sum Colonel Blotto. If the social payoff has rank-$r$ structure, then, for every fixed $r$, an $\varepsilon$-Nash equilibrium can be computed in time polynomial in $B_1,B_2,k$, and $1/\varepsilon$. Thus constant-rank two-player Colonel Blotto remains tractable despite its exponentially large pure strategy spaces. Finally, we study multiplayer winner-takes-all Colonel Blotto with player-specific battlefield values and uncover a sharp tie-breaking frontier. If every highest bidder receives her full battlefield value, an exact pure Nash equilibrium can be computed in polynomial time for arbitrary binary-encoded budgets. In contrast, under ordinary equal splitting among highest bidders, we prove that computing an inverse-polynomial-accuracy Nash equilibrium is PPAD-hard even with only five players. This resolves an open question posed in concurrent work by Bichler and Ghosh [BG26], who established PPAD-hardness in the same player-specific equal-splitting setting when the number of players grows with the instance and asked whether hardness persists for a constant number of players.

0.03

A Simple Algorithm Breaking the 1/3 Barrier for Approximate Nash Equilibria in Bimatrix Games

cs.GT cs.DM ·2026-10-04 ·Dongchen Li, Hanyu Li
similarity 0.61
Abstract

The PPAD-completeness of computing Nash equilibria in bimatrix games has driven extensive research into polynomial-time algorithms for $ε$-approximate Nash equilibria. Determining the strongest approximation guarantee achievable in polynomial time is a fundamental question in the complexity of approximate Nash equilibria. Despite sustained efforts, breaking the $1/3$ barrier has long been regarded as a difficult open problem. In this paper, we give an affirmative answer by proposing a simple, symmetric deterministic polynomial-time algorithm that has no tunable hyperparameters and achieves an approximation guarantee of approximately $0.30954+δ$. The main idea is to enrich the optimization framework of Tsaknakis and Spirakis with building blocks drawn from our work on strategy mixing and automated approximation analysis, yielding a new algorithmic structure that provides a conceptual explanation for the improved guarantee.

0.49

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.60
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

Equilibrium Numbers in Non-Square Bimatrix Games

cs.GT math.CO ·2026-09-21 ·Constantin Ickstadt, Thorsten Theobald, Bernhard von Stengel
theory similarity 0.60
Abstract · 32 pages

Bimatrix games may have an exponential number of mixed Nash equilibria if both dimensions of the game are allowed to grow. Bounds on their maximal number give structural insights that have been used to construct hard-to-solve games. We show new sharp or asymptotically sharp bounds on the (polynomial) number of equilibria for generic games where one dimension of the game is fixed and the number of strategies of the other player grows. These results go beyond the hitherto studied square games. Our methods employ combinatorial properties of polytopes, and recent obstructions that relate to the graph of those polytopes. For $n\ge5$, we construct $3\times n$ games that have all $2n+1$ vertices of the best-response polytope as equilibrium strategies, proved using a simple case of the 4-color theorem for planar graphs. Generic $4\times 5$ games are shown to have at most 17 equilibria, using computer calculations with existing datasets for all combinatorial types of the relevant polytopes. For $d\times n$ games, we construct games where all but a fraction of $O(1/n)$ of the maximum number of vertices are equilibrium strategies.

0.29

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

cs.GT cs.CCcs.DScs.LG ·2026-09-19 ·Ioannis Anagnostides, Weiqiang Zheng
theory similarity 0.59
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.

0.36

Fixed Sets and the Hardness of Computing Correlated Equilibria

cs.GT cs.CCcs.DScs.LG ·2026-10-20 ·Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm +1 more
similarity 0.59
Abstract · V2 adjusted cross-reference labels; no changes to the technical content

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 $f$ is a nonempty finite set $S$ such that $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.

0.14

Efficient Equilibrium Computation in Colonel Blotto Games

cs.GT cs.DSecon.TH ·2026-11-03 ·Martin Bichler, Abheek Ghosh
similarity 0.59
Abstract · 75 pages

Colonel Blotto is a fundamental resource-allocation game in which two players divide their budgets across battlefields, and the higher allocation on each battlefield wins its value. The problem of computing an equilibrium efficiently has remained unresolved for its classical continuous version with arbitrary budgets and with values that may vary across battlefields but are the same for both players. We give a fully polynomial-time approximation scheme that computes an $\varepsilon$-Nash equilibrium in time polynomial in the input length and $1/\varepsilon$, and nearly linear in the input length for fixed $\varepsilon$. For sufficiently balanced budgets and battlefield values, we also compute exact equilibria in linear time.

0.13