A new algorithm tackles equilibrium in the continuous Colonel Blotto game

Two rivals have fixed budgets and several battlefields to contest. Each divides a divisible resource among them. The higher allocation wins a battlefield’s value; a tie splits it equally. Allocating more to one battlefield leaves less available elsewhere.

This is the continuous Colonel Blotto game. In a preprint posted on November 3, 2026, Martin Bichler and Abheek Ghosh of the Technical University of Munich present an algorithm for computing approximate equilibria across the classical two-player model with arbitrary positive rational budgets and common rational battlefield values. Their general result allows battlefields to differ in importance, but requires both players to value each battlefield equally.

The work presents mathematical guarantees rather than measured performance benchmarks. Its preprint status should also distinguish the authors’ results from independently established or peer-reviewed conclusions.

What counts as a stable strategy?

An equilibrium here is generally not one fixed allocation. It is a pair of randomized strategies: each player draws a complete allocation from its own probability distribution. Neither can improve its expected payoff by changing strategy alone.

The authors compute an approximate version, called an epsilon-Nash equilibrium. After normalizing total battlefield value to one, neither player can gain more than epsilon in expected payoff through any feasible unilateral deviation. With epsilon equal to 0.01, for example, the permitted improvement is at most one hundredth of the total battlefield value.

Crucially, this guarantee covers continuous deviations, not merely bids on a selected grid. Every allocation sampled from the computed strategies must also respect its player’s budget. Being within budget only on average is insufficient.

Why finer grids can still fail

A natural shortcut is to restrict allocations to multiples of a small unit and solve that discrete game. The paper shows why this does not automatically solve the continuous problem.

At a tie, an arbitrarily small extra bid can change a player’s share of a battlefield from one half to the whole value. A grid instead requires an entire additional step, which may make several such changes unaffordable together.

The authors construct a two-battlefield example with equal values and budgets of one and two-thirds. For arbitrarily fine uniform grids, the restricted game has an exact equilibrium from which the smaller-budget player can improve its expected payoff by one-twelfth of the total value through an off-grid allocation.

This does not show that every grid-based approach fails. It shows that an arbitrary exact equilibrium of a finer discrete game need not become an approximate equilibrium of the continuous game.

Preserving the deviations that matter

The general algorithm uses finite representations more carefully. Against a strategy with finitely many possible bids, an opposing bid matters through which amounts it ties or exceeds. The construction preserves whether combinations of those ties and wins fit within the opponent’s budget, including the distinction between spending exactly the budget and leaving a little slack.

The algorithm combines multiplicative weights, an iterative reweighting method, with dynamic programming for budget-constrained allocation choices. It avoids explicitly enumerating the enormous sets of candidate allocations and responses. Its output describes distributions over complete feasible allocations, retaining the relationships between bids across battlefields.

The authors prove a fully polynomial-time approximation scheme: construction time is polynomial in the binary input length and in one divided by epsilon. For fixed epsilon, it is nearly linear in input length, up to logarithmic factors. However, the stated general bit-operation bound includes an inverse-sixth-power dependence on epsilon and a cubic dependence on the smaller of the battlefield count and one divided by epsilon. The guarantee therefore does not establish fast practical performance at high accuracy.

A faster exact result—with conditions

The paper also improves a more specialized approach based on General Lotto, a relaxation where budgets hold only in expectation. Turning its individual battlefield distributions into Blotto strategies requires coordinating them so that every complete allocation stays within budget.

Normalize the larger budget to one, the smaller to b, and total battlefield value to one. The relevant Lotto distributions can be coordinated feasibly exactly when the largest battlefield value is at most b divided by two. With equally valued battlefields, this becomes b at least two divided by the battlefield count.

Under that condition, the authors give exact equilibrium construction and sampling in linear time in the number of battlefields. This uses an idealized real-arithmetic model with exact continuous uniform random draws. Their finite-bit implementation instead produces rational allocations forming an approximate equilibrium, while spending each budget exactly on every draw.

The general approximation scheme does not cover arbitrary player-specific values or more than two players. A separate extension handles differing valuations only under a sufficient coupling condition. Better dependence on approximation accuracy, and broader general guarantees, remain open questions.