Efficient Equilibrium Computation in Colonel Blotto Games

Introduction

Colonel Blotto is a fundamental model of competition with limited resources, dating back to Borel’s work in 1921 [8]. In the classical game, two players allocate their budgets of a divisible resource across several battlefields. Each player’s total allocation must not exceed its budget. The players may have different budgets, and values may vary across battlefields, but each battlefield has the same value for both players. On each battlefield, the higher allocation wins its value, and a tie splits that value equally. Each player seeks to maximize the total value it wins.

Despite more than a century of study, computing approximate equilibria efficiently has remained an open problem for arbitrary budgets and battlefield values. We resolve this question with a fully polynomial-time approximation scheme (FPTAS) that computes an $\varepsilon$-Nash equilibrium in time polynomial in the binary input length and $1/\varepsilon$.

One approach to constructing Blotto equilibria starts from the General Lotto relaxation, in which the budget constraint holds only in expectation. Nash equilibria of General Lotto have been characterized [11]. To turn such an equilibrium into Blotto strategies, each player’s bid distributions on individual battlefields must be coupled into a joint distribution that respects its budget on every draw. [13] characterizes exactly when such couplings exist, shows that they yield a Blotto equilibrium, and gives an algorithm for computing and sampling an approximate equilibrium in this regime. Outside this regime, no pair of feasible strategies has these marginals, and an algorithm must find strategies with different marginals. Our approximation scheme removes this restriction.

Another natural approach is to discretize allocations and use an algorithm for computing equilibria in the discrete Blotto game [1, 4, 2]. However, a strategy on a grid assigns positive probability to individual bids, and an arbitrarily small increase above such a bid turns ties into wins. We give a two-battlefield game in which, for arbitrary fine uniform grids, the discretized game has an exact equilibrium from which one player gains $1/12$ of the total value by deviating to an allocation outside the grid Proposition 5.2. Thus, an exact equilibrium of a discretized game need not be an approximate equilibrium of the continuous game, however fine the grid.

Our results

For a game with $n$ battlefields, normalize the budgets to 1 and $b \in(0,1]$, and the positive common battlefield values $v_1,\ldots,v_n$ to sum to one. The budgets and values are rational, as is the approximation parameter $0 < \varepsilon< 1$. An $\varepsilon$-Nash equilibrium allows neither player to increase its expected payoff by more than $\varepsilon$ through any feasible deviation in the continuous game. Our algorithms construct strategy descriptions from which each player can independently sample an allocation satisfying its budget.

We give bounds in both the finite-bit and real-RAM models. The finite-bit model counts bit operations on binary input and uses independent random bits. Our real-RAM model allows exact arithmetic and comparisons on real numbers and, for sampling, independent uniform draws from $[0,1]$, each at unit cost.

An FPTAS for arbitrary budgets and battlefield values. We give a deterministic algorithm for computing an $\varepsilon$-Nash equilibrium (Theorem 5.1). Let $L$ be the total binary encoding length of the game input and $\varepsilon$, and let $n_* = \min\{n,1/\varepsilon\}$. The algorithm constructs the strategy descriptions in

bit operations, or

real-RAM operations.

Here $\widetilde{O}$ suppresses polylogarithmic factors. The construction takes time polynomial in the binary input length and $1/\varepsilon$, and nearly linear in the input length for fixed $\varepsilon$. Sampling an allocation takes $O(n+\log(1/\varepsilon))$ real-RAM operations. In the finite-bit model, sampling and writing a rational allocation take expected time polynomial in the input length and $1/\varepsilon$; Theorem 5.1 gives the detailed bound.

The approximation scheme searches for feasible strategies without fixing their marginal distributions in advance. For each player, we construct a finite set of candidate allocations that can support an approximate equilibrium. To check deviations against strategies supported on this set, we construct a second finite set of feasible allocations for the opponent. For every mixture of the player’s candidate allocations, this second set contains a best response in the continuous game. We compute the strategies without enumerating either set, combining multiplicative weights with dynamic programming to select feasible allocations.

A preliminary reduction to $O(1/\varepsilon)$ battlefields gives the dependence on $n_*$. Replacing $\varepsilon$ by a nearby power of two and rounding the values and budget ratio to numbers with short binary encodings make the dependence on $L$ additive. Transferring these strategies back to the original game requires care because small bid changes can cause large payoff changes at ties. We show how to preserve feasibility while controlling the loss in equilibrium accuracy.

We used ChatGPT to help optimize the FPTAS and improve its running-time bounds, including obtaining nearly linear dependence on the input length for fixed $\varepsilon$.

Exact equilibria from General Lotto marginals. Our second result gives a faster algorithm that computes an exact Nash equilibrium when

This is precisely the condition under which the General Lotto equilibrium marginals can be coupled into feasible Blotto strategies [13 Corollary 1]. For equal battlefield values, it becomes $b \ge2/n$. In this regime, computing an exact Nash equilibrium and sampling each allocation both take $O(n)$ time in the real-RAM model (Theorem 4.1). The sampling bound matches the $\Omega(n)$ time needed to write all $n$ allocation coordinates.

The algorithm of [13 Theorem 2] takes $O(n^2 + \varepsilon^{-4}\log(1/\varepsilon))$ arithmetic operations to sample from an $\varepsilon$-Nash equilibrium. Its construction reduces the coupling problem to at most four random variables and then approximates their joint distribution by discretization and tensor scaling. We give explicit exact couplings for these remaining variables and carry out the reduction in linear time per draw. This removes both the quadratic dependence on $n$ and the approximation cost in the real-RAM model.

A sampler restricted to rational allocations cannot always sample from an exact equilibrium, even for rational inputs. For example, with equal budgets and three equally valued battlefields, every equilibrium has continuous uniform marginal distributions [15 Theorem 2]. Our exact sampler uses the real-RAM model’s ability to draw independent uniform samples from $[0, 1]$.

Our construction also has a finite-bit implementation that computes an $\varepsilon$-Nash equilibrium and samples rational allocations satisfying the budgets on every draw (Corollary 4.5). With $k = \lceil\log_2(1/\varepsilon) \rceil$, constructing the samplers takes $\widetilde{O}(nL)$ bit operations, and each draw takes $\widetilde{O}((n + k)(L + k))$ bit operations.

When the players assign different values to the same battlefield, our coupling construction applies under the sufficient condition given for this setting in [13 Theorem 1]. Using their parameter search, we can test this condition and, when it holds, compute an exact equilibrium in $O(n \log n)$ operations, with $O(n)$ operations per allocation sampled (Theorem 4.6). For the parameter search, we augment the real-RAM model with a unit-cost operation that returns the exact real roots of a polynomial of degree at most three. With each player’s values normalized to sum to one, a finite-bit implementation computes an $\varepsilon$-Nash equilibrium and samples allocations from it in time polynomial in the input length and $\log(1/\varepsilon)$. The FPTAS discussed earlier (Theorem 5.1) requires each battlefield to have the same value for both players.

Further related work

Classical work constructs and characterizes equilibria in several continuous Blotto models. Gross and Wagner [10] construct equilibria for two battlefields with arbitrary budgets and for any number of equally valued battlefields with equal budgets. Macdonell and Mastronardi [MM15] characterize the full set of two-battlefield equilibria, and Roberson [15, 16] studies games with equal battlefield values and asymmetric budgets. Thomas [18] studies games with heterogeneous common values and equal budgets.

The coupling approach of [13] combines General Lotto equilibria [11] with conditions under which given marginal distributions can be coupled to have a constant sum [20]. Efficient sampling from continuous Blotto equilibria is also known in certain symmetric multiplayer settings [5]. Both [13] and [5] state that equilibrium existence follows from general theorems for discontinuous games. The hypotheses of the theorems they cite can fail in our model, so we prove directly the minmax equality used by our approximation scheme (Lemma 5.3).

Other approximation results for the continuous game give different guarantees. The strategies of [19] have an equilibrium error that decreases with the number of battlefields under certain conditions on the battlefield values. For every constant $c$, [3 Theorem 3.6] gives a polynomial-time approximation scheme for maximizing a player’s guaranteed expected payoff among strategies supported on at most $c$ allocations. Neither result gives, for every instance and every $\varepsilon> 0$, an $\varepsilon$-Nash equilibrium in time polynomial in the input length and $1/\varepsilon$. For discrete Blotto, [1, 4] give exact equilibrium algorithms polynomial in the number of battlefields and the integer budgets. The sampling and learning methods of [2] give $\varepsilon$-Nash equilibria with polynomial dependence on $1/\varepsilon$ and only polylogarithmic dependence on the budgets. These bounds concern integer allocations and do not themselves control deviations in the continuous game. In a different direction, [BG27] proves hardness of approximate equilibrium computation in discrete multiplayer games with player-specific values. Our FPTAS, in contrast, concerns two players with common values.

Model and preliminaries

There are two players, $A$ and $B$, and $n \ge1$ battlefields indexed by $[n] = \{1,\ldots,n\}$. Without loss of generality, players $A$ and $B$ have budgets $1$ and $b \in(0,1]$, respectively. Battlefield $i$ has a common value $v_i > 0$ for both players, with $\sum_{i=1}^{n} v_i = 1$. For a budget $c \ge0$, let

The pure strategy spaces of $A$ and $B$ are $\mathcal{X}(1)$ and $\mathcal{X}(b)$, respectively. The player who allocates more resources to a battlefield receives its value. In a tie, including when both allocations are zero, each player receives half its value. Let $h(s,t)$ denote the share received by a player who bids $s$ against a bid $t$:

The players’ payoffs at $x \in\mathcal{X}(1)$ and $y \in\mathcal{X}(b)$ are

In particular, $u_A(x,y) + u_B(x,y) = 1$ for every pair of feasible allocations.

Nash equilibrium. A mixed strategy is a probability distribution on the player’s pure strategy space. We denote the strategies of $A$ and $B$ by $\mu_A$ and $\mu_B$. For independent allocations $X \sim\mu_A$ and $Y \sim\mu_B$, the expected payoffs are

We use $u_A(x,\mu_B)$ and $u_B(\mu_A,y)$ when one player chooses a pure strategy. Each player’s regret is the supremum increase in expected payoff from a unilateral deviation:

For $\varepsilon\ge0$, an $\varepsilon$-Nash equilibrium is a pair $(\mu_A,\mu_B)$ with both regrets at most $\varepsilon$; a Nash equilibrium is the case $\varepsilon= 0$. The approximation is additive in the normalized payoffs. Pure deviations suffice because the payoff of a mixed deviation is an average of the payoffs from pure deviations. We use suprema since the payoff is discontinuous at ties and a best response need not be attained.

To bound these regrets, it suffices to consider deviations that spend the full budget. Any deviation in $\mathcal{X}(c)$ can be made to spend $c$ by adding the unused budget to one coordinate, which weakly increases the payoff against every allocation of the opponent.

For a mixed strategy $\mu$, let $U(\mu;c)$ denote the supremum expected payoff of an opponent with budget $c \ge0$:

Since the game is constant-sum, adding the regret definitions gives

Since each regret is nonnegative, $U(\mu_B;1) + U(\mu_A;b) \le1 + \varepsilon$ implies that $(\mu_A,\mu_B)$ is an $\varepsilon$-Nash equilibrium.

Marginal distributions and approximation

Expected payoffs depend only on the marginal distributions of allocations to individual battlefields, although feasibility still requires a joint distribution satisfying the budget constraint. If the opponent’s allocation to a battlefield is a random variable $Y$ with cumulative distribution function (CDF) $F$, then bidding $s$ on that battlefield gives expected share

For a mixed strategy $\mu$, write $F_{\mu,i}(t) = \mathbb{P}_{X \sim\mu}(X_i \le t)$ for its marginal CDF on battlefield $i$. We measure the difference between two mixed strategies $\mu$ and $\nu$ by