CS Paper Radar

Efficient Equilibrium Computation in Colonel Blotto Games

Martin Bichler, Abheek Ghosh

cs.GT cs.DSecon.TH ·submitted 2026-11-03 17:06 UTC · v1

Abstract

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.

Comment
75 pages

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

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.77
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 Resource Allocation Tournament

cs.GT math.OCecon.TH ·2026-10-22 ·Adam Nathaniel, Refael Hassin
similarity 0.70
Abstract

We introduce and analyze a round-robin simultaneous resource allocation contest, motivated by sports leagues and other competitive environments where agents must distribute limited resources across multiple encounters. Players allocate resources in advance to matches against all opponents, and match outcomes are determined by relative allocations. We study two payoff schemes: total points, where players accumulate rewards for each win, and winner-takes-all, where only the tournament winner is rewarded. For three players, we provide complete equilibrium characterizations under both schemes. For four or more players, we show that the total points payoff admits Blotto-type equilibria, while the winner-takes-all payoff requires numerical and algorithmic analysis. To address this, we develop a best-response dynamics algorithm with stochastic inertia and use it to approximate equilibria in games with four and five players.

0.26

Efficient Nash Equilibrium Computation for Cybersecurity Games

cs.GT cs.AI ·2026-09-16 ·Michael Lanier, David Farmer, Yevgeniy Vorobeychik
theory similarity 0.67
Abstract

Game-theoretic analyses of cyber defence often compute equilibria of games whose payoffs exist only as the output of a simulator. Iterative equilibrium-finding methods grow a set of attacker and defender policies and need the payoff of every attacker--defender pair, so they are bottlenecked by payoff estimation: each payoff costs many simulator runs. We introduce Regret-Weighted Payoff Sampling (RWPS), which spends a fixed simulation budget on the payoffs the equilibrium actually depends on and predicts the rest with a model trained on every payoff measured so far. Standard error bounds for estimated games are driven by the worst-estimated payoff, so they cannot credit an estimator that is inaccurate only where accuracy does not matter. We prove a bound that weights payoff errors by the opponent's equilibrium strategy, a certificate that can be computed from simulated payoffs alone, and a condition under which errors in the predicted payoffs cannot change either player's regret. On three synthetic general-sum games, one of them a Colonel Blotto game of military resource allocation, the new bounds are four to six times tighter than the standard one, and RWPS finds less exploitable equilibria than minimum-regret-first search, information-gain search and progressive sampling at the same budget. On two cyber-defence simulators, CyGym and a new game whose hosts are LLM agents exposed to prompt injection, it gives the least exploitable equilibria at the smallest budgets.

0.26

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

The Game of Marginal Utilities

cs.GT math.OC ·2026-08-11 ·Isaac M. Sonin, Georgy Gaitsgori, Yaakov Malinovsky
theory similarity 0.65
Abstract · 29 pages

We study a noncooperative resource-allocation game in which $m$ players distribute fixed resources among $n$ projects and the payoff of player $j$ is given by \[ F^j(x) = \sum_{i=1}^n \frac{a_i x_i^j}{b_i+\sum_{\ell=1}^m x_i^\ell}, \] where $a_i$ and $b_i$ are project parameters, while $x_i^j$ is the amount of resources player $j$ allocates to project $i$. This specification combines diminishing returns with congestion generated by competitors. We prove that the game has a unique Nash equilibrium and characterize it by an equimarginal principle. We show that, after the projects are ordered by $a_i/b_i$, each player invests in an initial segment of projects, and these segments are nested across players, so the equilibrium decomposes into consecutive activity zones; players with larger resources invest weakly more in every project. In the fully active regime, where every player invests in every project, we reduce the equilibrium to a single scalar nonlinear equation for the aggregate marginal-utility rate; all individual marginal rates, investments, and payoffs then follow from explicit formulas. We also provide a projected marginal-utility algorithm with global linear convergence under an explicit step-size condition, together with a structure-exploiting \textit{Block Pandora} algorithm that reconstructs and certifies the equilibrium conditional on a proposed nested cutoff structure.

0.10

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

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