Five Front Battle

Question

Two generals are fighting a five front battle. Each general has 1 unit of army, which he divides into five separate armies that he sends to the five fronts. If one general sends more army to a front than the other, then the other army instantly gives up and the front is taken over by that general. If they send exactly equal amounts of army to a front, then the leaders of the armies play a game of Backgammon to determine the owner of the front. Whichever general takes over at least three of the fronts wins the battle (the other general gives up).

Neither general has any spies, and they split their armies simultaneously, so each general would like you to find him a probabilistic strategy that guarantees that he will not lose the battle more than half of the time.

Background: I found the three front version of this problem on the xkcd forums. I don't know if generalizations of the problem to larger numbers of fronts have been considered before.

As a starting point, here is a class of strategies that can never work:

Suppose that you have a distribution such that the expected number of fronts you win is at least $\frac52$ regardless of the other player's strategy. Then you will lose against a random permutation of the splitting $(0, 0, \frac3{10}, \frac3{10}, \frac25)$ more than half of the time.

Proof: Assume your strategy has probability $f(x)$ of sending at least $x$ units of army to a front. Then expecting to win $\frac52$ fronts implies that for any $a + b + c+d+e = 1$, we have $f(a)+f(b)+f(c)+f(d)+f(e) \ge \frac52$, and combining this with the fact that the average amount of army sent to a front is $\frac15$ it isn't hard to show that the number of armies sent to any particular front must be uniformly distributed between $0$ and $\frac25$. Thus, the number of fronts that you expect to win against a random permutation of $(0, 0, \frac3{10}, \frac3{10}, \frac25)$ is exactly $\frac52$.

It isn't hard to calculate that the probability of winning the battle is given by (E(fronts won) - Pr(win even number of fronts) - 1)/2. So, we just need to check that the chance of winning an even number of fronts is more than half. To start off with, we will always lose the front he sends $\frac25$ armies to, and win the fronts he send $0$ armies to. Thus, the probability of winning two fronts must be at least the combined probability of winning three or four fronts (since you never win one just one front), so you will lose more than half of the time as long as you have a nonzero chance of winning four fronts, and you will have a nonzero chance of winning four fronts as long as you send at least $\frac3{10}$ units of army to two of the fronts. But the chance of sending at least $\frac3{10}$ to a front is $f(\frac3{10}) = \frac14$, and if your strategy never sends $\frac3{10}$ to two fronts at a time then the chance of sending at least $\frac3{10}$ to a particular front would be at most $\frac15$, which is impossible.

Answer 1

I am reposting notzeb's solution to the 3 front case here, and making some comments on it. In particular, I will point out that the solution is not unique; while notzeb used fractal methods, I will give a piecewise smooth solution using the same ideas.

Idea of solution:

I claim that it is enough to find any probability distribution on $\{(p,q,r): p+q+r=1, \ p,q,r \geq 0 \}$ whose projection to each coordinate is the uniform measure on $[0,2/3]$.

Proof that such a measure works:

(For simplicity, I disregard ties.) Observe that it is impossible for either general to win on all fronts. Therefore, if I find a strategy that guarantees that I am expected to win at least 1.5 fronts against any opposing strategy, this means that I have probability at least 1/2 of winning 2 fronts against any opposing strategy. (This logic does not extend to the 5 front case.)

Suppose my enemy sends $p$ troops to the first front. I beat him with probability $\max(1-(3/2)p, 0)$. By linearity of expectation, if my enemy sends troops $(p,q,r)$, my expected number of victories is $$\max(1-(3/2)p, 0)+\max(1-(3/2)q, 0)+\max(1-(3/2)r, 0)$$ $$\geq 3-(3/2)(p+q+r) = 3/2.$$ If my opponent adopts a mixed strategy, linearity shows that I still have expected number of victories at least $3/2$. QED

notzeb's measure:

Take the triangle of possible solutions and inscribe a hexagon in it, with vertices at the permutations of $(0,1/3,2/3)$. All our solutions will be inside that hexagon.

Now, take that hexagon and place 6 smaller hexagons in it as shown below.

6 Hexagons in 1 http://www-math.mit.edu/~speyer/3front.png

Choose one of those 6 hexagons uniformly at random. Place 6 smaller hexagons inside that one, and choose one of these uniformly at random again. Keep going. The hexagons shrink in size each time; the limiting point is your army distribution.

Notice that the space of possible solutions is a Sierpinski-gasket-like figure, of Hausdorff dimension $\log 6/\log 3$. It is cute to observe that the white star of David in the center becomes a Koch snowflake of excluded points in the final solution.

My alternate measure

Inscribe a circle in the triangle. On that circle, place the measure $dA/\sqrt{1-r^2}$, as described in Harald Hanche-Olsen's answer to a different question.

Answer 2

This is an example of a class of games known as 'Colonel Blotto' games. Wikipedia claims that the paper Roberson, B. (2006), “The Colonel Blotto Game,” Economic Theory 29, 1–24. provides a solution for any number of battlefields and any number of resources, but I haven't independently confirmed this.

Update: In response to zeb's comment below, while it is true that the game described is different than Blotto, it is also the case that, by the symmetric nature of the problem, a strategy will be optimal for either game if and only if the expected number of victories is $n/2$, regardless of the opponent's strategy. So solving Blotto is equivalent to solving the question which was asked.

I also got around to looking at Roberson's paper, and he does indeed solve the problem. He first proves that any distribution which projects to Uniform$[0,2/n]$ in each coordinate will work. Then he constructs such a distribution for any $n$. (Actually he does quite a bit more, since he does not assume that the two players have equal resources.) The details are a bit much to put in an MO post, but anyone interested should check it out; the paper is not very long and not too hard to read.