CS Paper Radar

Hardness Amplification for Approximate Nash Equilibrium with Constantly Many Players

Xiaotie Deng, Ningyuan Li, Zihe Wang, Jie Zhang

cs.GT cs.CC ·submitted 2026-10-19 00:26 UTC · v2

Abstract

For every fixed integer $k\ge2$ and fixed parameters $δ,\varepsilon\in(0,1)$ and $η\in[0,1)$, we give a deterministic polynomial-time reduction from finding a $δ$-approximate Nash equilibrium ($δ$-ANE) in a $k$-player game $G$ with payoffs in $[0,1]$ to finding an $(\varepsilon,η)$-weak approximate Nash equilibrium (weak ANE) in a game $H$ with $C$ players, where $C$ depends only on $k,δ,\varepsilon,η$, independently of the action-set sizes. The constructed game is symmetric with binary payoffs. The games and strategies are represented by complete payoff tables and probabilities, with rational entries encoded in binary. Consequently, the existence of deterministic polynomial-time weak-ANE algorithms at one fixed pair of parameters $\varepsilon\in(0,1),η\in[0,1)$ for every fixed number of players would give deterministic polynomial-time $δ$-ANE algorithms at every fixed approximation parameter $δ\in(0,1)$ and number of players. Under deterministic PPAD-ETH, combining our reduction with Rubinstein's hardness result (FOCS 2016) for bimatrix games at some fixed approximation parameter $γ_0\in(0,1)$ rules out a deterministic algorithm for $(\varepsilon,η)$-weak ANE with running time $N^{O((\log N)^{1-ξ})}$ for any fixed $ξ\in(0,1)$. This holds for every fixed $\varepsilon\in(0,1)$ and $η\in[0,1)$ at a suitable constant number $C$ of players, where $N$ is the binary encoding length of the constructed game's complete payoff table.

Closest papers

Nearest neighbours by meaning across the whole index.

The Complexity of Computing Nash Equilibria in Colonel Blotto Games

cs.GT cs.CC ·2026-10-05 ·Vasilis Pollatos, Andreas Kontogiannis
theory similarity 0.69
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

Breaking the One-Player Extension Barrier: History-Aware Repair for Multiplayer Approximate Nash Equilibria

cs.GT ·2026-11-04 ·Jinqi Tang, Shihong Ding, Cong Fang
similarity 0.68
Abstract

Computation of Nash equilibria is a central problem in algorithmic game theory, yet exact equilibrium computation is $\mathsf{PPAD}$-complete even for two-player games. This hardness motivates the study of polynomial-time algorithms for approximate Nash equilibria. While substantial progress has been made for two-player and three-player games, existing algorithms for general $m$-player games have largely relied on repeatedly applying one-player extension starting from improved fixed-player algorithms. Such improvements can at best strengthen the classical $1-1/m$ guarantee to $1-1/(m-c)$, for some constant $c$ independent of $m$. We break this long-standing barrier by developing an iterative algorithm that directly tackles general $m$-player games and achieves a $(1-(σ_{\star}-ε)/m)$-approximation for fixed $ε> 0$ and sufficiently large $m$, where $σ_\star\approx1.5867$ is the unique root in $(1,2)$ of $σ_\star^3-19σ_\star^2+27σ_\star+1=0$. Our approach rests on a novel iterative descent-and-repair framework that allows multiple rounds of repair. At the heart of our analysis is a new potential function inspired by continuous-time dynamics, which certifies progress across iterations and ensures polynomial-time termination. Our results highlight the power of history-aware, iterative repair in breaking approximation barriers for multiplayer games.

0.13

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

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

On Existence and Computational Complexity of Quasi-strict Equilibria

cs.GT ·2026-11-04 ·Kristoffer Arnsfelt Hansen, Xinhao Nie
similarity 0.66
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 Exact and Approximate Nash Equilibria in Anonymous Games

cs.GT ·2026-10-12 ·Zhengyang Liu
theory similarity 0.66
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

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

Simple Strategy-Iteration with Dantzig's Rule is not Strongly Polynomial on Turn-Based Deterministic Games

cs.GT cs.CCmath.OC ·2026-10-19 ·Sanyou Mei
theory similarity 0.64
Abstract

We study turn-based deterministic zero-sum games with discounted and long-run average costs. For discounted costs, we establish exponential and superpolynomial iteration lower bounds for the simple strategy-iteration method with Dantzig's rule under unrestricted costs and unit weights, respectively. To the best of our knowledge, we establish for the first time that the method is not strongly polynomial, and this remains true even when all action costs belong to $\{-1,0,1\}$. For long-run average costs, we extend the Dantzig counterpart in~\cite{zhongye2026} to the two-player setting and prove that it terminates at an optimal strategy profile. However, a similar counterexample construction establishes an exponential iteration lower bound for termination with unrestricted costs. This construction does not extend to unit weights, for which we prove that the algorithm admits a strongly polynomial implementation.

0.29