Two colonels and a linear programme

In 1921 Émile Borel described a game that has since been called Colonel Blotto. Two colonels each command the same number of soldiers and must divide them, at once and in secret, among a number of battlefields. On each field, whoever sends more soldiers wins it; equal numbers win nothing for either side. A colonel’s score is the number of fields won minus the number lost. Elections fought across several constituencies, budgets split across markets, and security spread across targets all have this shape, and Borel chose it because it is the simplest game in which there is obviously no best plan.

The game is also the cleanest large example of what the value from both sides proved for small ones: a zero-sum game has a value that both players can secure once they are allowed to choose at random, and the two guarantees meet. Here the two guarantees are a linear programme and its dual, solved exactly, and the solution has structure nobody would guess from the rules.

No plan survives being read #

A pure strategy is a division: with six soldiers and three fields, a list such as $(3, 2, 1)$, and there are 28 of them. The first thing to establish is that every one of them can be beaten.

The counters follow one rule: concentrate on the fields the target holds lightly, and abandon the one it holds most. Against $(6, 0, 0)$, send one soldier each to the two empty fields and keep four for show. Against the even split $(2, 2, 2)$, send three to two fields and nothing to the third. Against $(3, 2, 1)$, send four to the field with three and two to the field with one, and give up the field with two. Whatever a colonel commits to, an opponent who knows it wins.

That rules out a pure equilibrium at once. In a pair of divisions where neither colonel wants to change, each division would be a best reply to the other; but the best reply to any division wins, so both colonels would be winning, which a zero-sum game does not allow. The only way to have a plan that cannot be read is to choose it by chance.

The colonel’s linear programme #

A mixed strategy is a probability for each division. Against a particular opposing division $y$, a mixture $p$ earns on average $\sum_x p_x A(x, y)$, where $A(x, y)$ is fields won minus fields lost when $x$ meets $y$. The colonel wants the largest guarantee $v$ that holds whatever the opponent does:

$$\text{maximise } v \quad \text{subject to} \quad \sum_x p_x A(x, y) \ge v \text{ for every } y, \qquad \sum_x p_x = 1, \quad p \ge 0.$$

Every constraint is linear in the unknowns $p_x$ and $v$, so this is a linear programme, with one unknown for each of the colonel’s divisions and one constraint for each of the opponent’s. The opponent’s problem is the mirror image — the smallest $w$ that its mixture $q$ can hold the first colonel to, with $\sum_y q_y A(x, y) \le w$ for every $x$ — and written out, it is exactly the dual of the first programme. Linear programming duality then says that the two optima are equal: $v = w$. That equality is John von Neumann’s minimax theorem of 1928, and it is the same theorem as strong duality, arrived at from the side of games instead of the side of optimisation.

The figures solve the programme by the simplex method. With nine soldiers each, both colonels have 55 divisions, the programme has 55 unknowns and 55 constraints, and the final tableau gives the first colonel’s mixture, the second colonel’s mixture and the value, all at once — the opponent’s mixture appears in the tableau as the prices of the first colonel’s constraints, which is what the worth of a constraint means in a game. The value is nought, as it must be in a symmetric game: neither colonel can expect to win more fields than he loses.

Seven divisions, each number once #

The hero’s mixture is the surprise. Of 55 possible divisions of nine soldiers, the optimal mixture the simplex method finds uses only seven, each with probability one seventh:

$$(6,3,0),\ (5,0,4),\ (4,4,1),\ (3,1,5),\ (2,5,2),\ (1,2,6),\ (0,6,3).$$

Read them field by field. The first field receives 6, 5, 4, 3, 2, 1 and 0 — each number from nought to six exactly once. So does the second field, in the order 3, 0, 4, 1, 5, 2, 6, and so does the third, 0, 4, 1, 5, 2, 6, 3. The seven divisions are a pattern in which every field’s allocation is spread perfectly evenly over the numbers from nought to six, and no field ever receives more than six soldiers, two thirds of the army.

That is not a coincidence of the arithmetic. Borel solved the game with infinitely divisible armies and three fields in 1938, with Jean Ville, and the solution has exactly this property: each field’s share is spread evenly between nought and twice the fair share. With nine soldiers the fair share is three and twice it is six, and the computed mixture reproduces Borel’s continuous answer exactly, on the whole numbers. The pattern is also a small piece of combinatorial design. From one division to the next in the list, the first field’s number goes down by one and the other two go up by four, all counted round a dial of seven, so the three steps add to seven and the total stays at nine — the way the rows of a cyclic Latin square step through its symbols. The hero shows the seven points sitting on a tilted lattice inside the larger triangle of all divisions.

With six soldiers the fair share is two and twice it is four, and again the optimal mixture never sends more than four to any field. Its seven divisions give the first field 4, 3, 3, 2, 1, 1 and 0: an average of two, the fair share, but not an even spread, because seven divisions cannot use each of the five numbers from nought to four equally often. The theory of the game with whole soldiers, developed by Sergiu Hart in 2008, shows that the continuous solution is approached as the armies grow, with exact even spreads available when the number of soldiers fits the number of fields in the right way.

Two certificates that meet #

The claim that the mixture is optimal is checked, not assumed. Against each of the opponent’s 55 pure divisions, the first colonel’s mixture earns some average number of fields won minus lost, and optimality means that every one of those numbers is at least the value.

The bars never go below the line, which is the first colonel’s certificate: whatever the opponent does, this mixture loses nothing on average. Against 37 of the 55 replies the mixture is held exactly to the value; against the other 18 it wins something. The opponent’s optimal mixture — the solution of the dual programme, read from the same tableau — puts weight on 15 divisions, and every one of them is among the 37 where the first colonel’s guarantee is tight. That is complementary slackness: a reply the opponent actually uses must be one against which the first colonel’s mixture does no better than the value, because otherwise the opponent would be giving something away. The same is true in the other direction, and together the two conditions are a certificate that neither mixture can be improved.

The opponent’s 15 divisions and the first colonel’s 7 are different sets, although the game is symmetric. Optimal mixtures are not unique here — any mixture of optimal mixtures is optimal, and the simplex method stops at a corner of the set of them — and the two programmes, solved together, simply stopped at different corners. Swapping the roles would give the opponent the first colonel’s seven.

Borel’s even spread #

The even spread is easiest to see one field at a time, with a larger army.

With twelve soldiers the computed mixture sends 0, 2, 4, 6 or 8 soldiers to a field, each with probability one fifth, and never more than eight. That is Borel’s even spread over $[0, 8]$, taken in steps of two: the average is four, the fair share, and the spread is as wide as it can be without any field getting more than two thirds of the army. Other optimal mixtures exist that use the odd numbers as well; this is the one at the corner where the simplex method stopped, and its regularity says that the corners of the set of optimal mixtures are themselves highly structured.

Why should the spread be even, and why should it stop at twice the fair share? Because any lump in the distribution is an invitation. If one colonel sent exactly three soldiers to a field unusually often, the other could send four there unusually often and win it. An even spread gives the opponent no number worth aiming at. And sending more than twice the fair share to a field is wasteful: it wins that field, but the soldiers come from the other two, which then hold less than half the army between them and are easily taken.

Why an even spread cannot lose #

The even spread has a two-line proof in the continuous game, and the proof explains both of its features at once. Suppose one colonel sends to a given field an amount $X$ spread evenly between nought and $2a$, where $a$ is the fair share, and the other sends any amount $Y$ at all, random or not, as long as its average is $a$. If $Y$ is some number $y$ no larger than $2a$, the chance that $X$ exceeds it is $1 - y/2a$ and the chance that it falls short is $y/2a$, so the first colonel’s expected result on that field is

$$\Big(1 - \frac{y}{2a}\Big) - \frac{y}{2a} = 1 - \frac{y}{a}.$$

If $y$ is larger than $2a$ the first colonel loses the field for certain, a result of $-1$, which is more than $1 - y/a$. So in every case the result is at least $1 - y/a$, and averaging over $Y$ gives at least $1 - \mathbb{E}[Y]/a = 0$. Against an even spread, no allocation with the right average can win a field more often than it loses it.

The first feature is the evenness: a linear expected result $1 - y/a$ is what makes the average of $Y$ the only thing that matters, and only a uniform distribution has a winning chance that falls linearly. The second is the cap at $2a$: an amount above it buys nothing beyond certain victory on that field, while costing soldiers that the average requires to be somewhere else. What remains for the full game is to arrange the three fields’ even spreads so that the soldiers always add up to the army, and that is where the geometry of the triangle comes in — Borel and Ville found such an arrangement for three fields, and the nine-soldier mixture is a whole-number version of it. Sergiu Hart’s name for the relaxed game, in which each field is played separately and only the averages are tied together, is General Lotto, and its solution is exactly this argument.

The prices in a game #

Duality has a reading in every application, and in a game the reading is unusually literal. In the first colonel’s programme each constraint says: against this opposing division, earn at least $v$. The dual variable on a constraint is the rate at which the optimal value would change if that constraint were relaxed — and here relaxing the constraint for division $y$ means caring a little less about what happens against $y$. The constraints with positive prices are the divisions the first colonel’s guarantee is really built against, and normalised to add to one, those prices are the opponent’s optimal mixture. The opponent’s best way to play is the first colonel’s list of worries, weighted by how much each one costs.

This is the content of prices at every corner turned into a strategy. A corner of the first colonel’s feasible region is a mixture at which some set of constraints holds with equality, and the simplex method walks from corner to corner, raising the guarantee at each step, until the prices it carries are all of the right sign. At that moment they are a mixture for the opponent, and the walk has solved both colonels’ problems at once.

What an extra soldier is worth #

With unequal armies the value is no longer nought, and the programme computes it just as easily.

One extra soldier, nine against eight, is worth a third of a field on average. Four extra soldiers, twelve against eight, are worth exactly one field. With fourteen against eight the stronger colonel wins on average 1.27 fields more than he loses, still well short of all three: an opponent with eight soldiers, choosing at random, can always concentrate on one or two fields and win them some of the time. The curve is roughly linear for small advantages and bends as the advantage grows, and the weaker side’s losses grow faster than the stronger side’s gains — four soldiers against eight lose 1.44 fields on average — because a small army spread over three fields is easily outnumbered everywhere.

The asymmetric game is where most of the theory lives. Brian Roberson solved the continuous version with unequal budgets in 2006, and his solution has the stronger colonel spreading each field evenly while the weaker one gives up some fields entirely, at random, and spreads what is left.

Three fields and twelve soldiers at most #

Three fields only. With $K$ fields and $S$ soldiers the number of divisions is $\binom{S + K - 1}{K - 1}$, and the programme grows with its square. Three fields and twelve soldiers is 91 divisions; ten fields and a hundred soldiers is over four trillion, and no direct linear programme can touch it. The large games are solved by exploiting symmetry — every optimal strategy can be averaged over permutations of the fields — and by working with the distribution of one field’s allocation rather than with whole divisions.

One optimal mixture among many. The mixtures drawn are corners of the set of optimal mixtures. Their striking regularity — seven divisions with each number once, a spread in steps of two — belongs to those corners. Other optimal mixtures exist, and some of them look much less tidy.

Exact arithmetic is not used. The simplex method runs in floating point, and every mixture is checked against every pure reply to within $10^{-7}$. That check is what makes the result trustworthy rather than the arithmetic, and for larger armies, where the programme becomes more degenerate, the computations here stop at twelve soldiers because the floating-point tableau stops passing it.

Still open: many fields, unequal fields #

What are the optimal strategies of the discrete game with many fields? For the continuous game with equal armies Borel’s even spread is the answer for every number of fields, and for unequal armies Roberson’s solution covers it. For whole soldiers the picture is more delicate: equilibrium strategies are known for particular relations between the number of soldiers and the number of fields, and in general they are found by computation. Fields of unequal value — a large constituency and several small ones — change the game again, and with weighted fields even the continuous game has no closed-form solution in general.

The other open direction is about opponents who are not optimal. Against a colonel who spreads soldiers in some predictable human way, the equilibrium mixture still guarantees the value but may leave a great deal on the table, and the best reply to a particular habit can look nothing like Borel’s even spread. That gap, between the guarantee a mixture gives and the advantage a reader of the opponent can take, is the same one the best reply to the past explored for small games: an equilibrium is a guarantee against the worst opponent, not a plan against the one actually faced.