The Colonel Blotto game

This is an interesting game I found in the book Introduction to game theory by Peter Morris that reminds me about the board game Risk.

The Colonel Blotto problem is a zero-sum game about how to best position resources. While Colonel Blotto games are described in a military context, I will explain in future articles some of its useful applications in sports, advertising, elections, and many other areas.

Today I want to highlight a specific Colonel Blotto game that is convenient to solve mathematically.

A simple example of a Colonel Blotto game

Colonel Blotto is planning his attack for the next day. He wishes to capture 2 different locations, and he has 4 regiments of troops.

The opposing commander, Colonel Lotso, also wishes to attack those 2 locations, and he has 3 regiments.

To make the problem precise, it is necessary to ascribe payoffs to possible outcomes.

Let’s say that if both send troops to the same site, the person who sent more troops will win the site.

Specifically, if one Colonel sends x troops, and other sends a lesser number y, then the Colonel who sent x regiments will win. The payout will be equal to y + 1: the Colonel gets y points for defeating that number of enemy troops, plus he gets 1 point for securing the location.

For example, if Colonel Blotto sent all 4 troops to one site, and Colonel Lotso all 3 to the same site, then Colonel Blotto would win the battle and get 4 points because he defeated 3 of Lotso’s regiments and got 1 point for securing the location.

If each sent all of their troops to different sites, however, then both would gain a location but not defeat any enemy troops. Each Colonel would get a location, but neither gains an advantage, so the net payout to each would be 0.

If both Colonels play strategically, how should they distribute their troops?

Solution to the Colonel Blotto game

Colonel Blotto has 5 strategies at his disposal: he can send 4 troops to either location, he can send 3 to one location and 1 to another, or he can send an equal number of troops 2 to each location. We will abbreviate these in set notation (4, 0), (0, 4), (3, 1), (1, 3), and (2,2).

By similar reasoning, Colonel Lotso has 4 strategies at his disposal that can be abbreviated (3, 0), (0, 3), (2, 1), and (1, 2).

We will write out the 5 x 4 matrix for the set of strategies and diligently calculate the payout for each battle. Since this is a zero sum game, we will write the payouts in terms of Colonel Blotto, and note that Colonel Lotso’s matrix would have the opposite values.

(The matrix displays net payouts to each site, so careful accounting is required to calculate some of the payouts. For example, consider the strategy (4,0) versus (2,1). Blotto wins the first site and gets a total of 3 points. But Lotso wins the other site and gets 1. So the net payout to Blotto is 3-1 = 2).

We can use a handy zero gum game solver to figure out the optimal strategy.

Colonel Blotto will play (4,0) with probability 4/9, he plays (0, 4) with probability 4/9, and he will play (2,2) with probability 1/9. He never plays (3, 1) or (1, 3).

Colonel Lotso does not have a unique mixed strategy. He can actually play a variety of mixed strategies. The symmetric solution, as explained in Introduction to game theory, is that he will play both (3,0) and (0,3) with probability 1/18, and he will play both (2,1) and (1,2) with probability 4/9.

Interpreting the solution

When both are playing their optimal strategy, Blotto can expect a payout of 14/9. This makes sense that Blotto has a positive payout because he has 1 extra regiment and should be favored.

The solution indicates that Blotto should concentrate his troops to specific sites and occasionally split his troops, just to make sure that Lotso cannot steal a location easily.

Lotso responds by doing the opposite. Lotso cannot win against Blotto in the numbers game, so Lotso has to spread his troops out and hope to secure an undefended location with 1 regiment. Occasionally Lotso will deploy all his troops to one site or the other, just so that Blotto cannot win by spreading his troops evenly all the time.