23
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I have to point out that the problem with 3 fronts is not solved in the link, the given strategies all perform worse than needed. $\endgroup$
    – Thorny
    Jan 7, 2010 at 10:05
  • 3
    $\begingroup$ Are the following comments correct? Perhaps a game theorist can back me up or shoot me down. The problem above is just a 2-player zero sum game, and the space I can play on is a compact convex set, so general theory tells me that there is a compact convex subset and a probability distribution on this subset that will do the job you want (and I think one of the possibilities for the subset will be defined by linear equations and inequalities and the probability distribution on this set can I think even be taken to be Lebesgue measure or indeed any measure at all)... $\endgroup$ Jan 7, 2010 at 11:21
  • 1
    $\begingroup$ The space of probability distributions on the standard triangle $x_1+x_2+x_3=1$ is not finite dimensional, so I would not place great hopes on a computer-based solution. It is not clear at all what kind of probability distribution would be a good candidate for satisfying the requirements, either. $\endgroup$
    – Thorny
    Jan 7, 2010 at 11:48
  • 4
    $\begingroup$ A nice computer experiment might be to replace the game by a discrete approximation where each general has N soldiers that cannot be subdivided. This is a finite dimensional, zero sum, two player game, so there must be software to find a minimax strategy. Looking at the limit of these strategies as N goes to infinity might give us some insight. $\endgroup$ Jan 7, 2010 at 13:28
  • 3
    $\begingroup$ @Thorny: For 3 fronts, notzeb's final solution works. forums.xkcd.com/viewtopic.php?f=3&t=43065#p1702833 Of course, he may have posted this after you made your comment. $\endgroup$ Jan 7, 2010 at 16:31

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Amusingly, I once wrote a puzzle mit.edu/~puzzle/06/puzzles/paris/drop_everything about reconstructing discrete measures from the knowledge of their projections in three different directions. $\endgroup$ Jan 7, 2010 at 17:55
  • $\begingroup$ What is a cuckoo bird? $\endgroup$
    – zeb
    Jan 8, 2010 at 1:39
  • $\begingroup$ I'm not sure whether that is a question or whether you are pretending to be on Jeopardy. If the former, see wikipedia. $\endgroup$ Jan 8, 2010 at 11:48
  • $\begingroup$ I think he's on Jeopardy, actually ... $\endgroup$
    – aorq
    Feb 5, 2010 at 5:49
1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ This is a different game - in the Colonel Blotto game, you are trying to maximize the number of fronts won, while in this game you only care about whether you win more fronts than the other guy. The Colonel Blotto game is much easier than this one... you don't have to worry about correlations between the fronts. $\endgroup$
    – zeb
    Feb 16, 2010 at 3:23
  • 2
    $\begingroup$ Jason, you are wrong. As zeb says in his original post, if you play a strategy which projects to Uniform(0,2/5), then you will lose against my strategy of playing a random permutation of (0,0,3/10,3/10,2/5). For simplicity, I'll analyse the case that your strategy projects to the uniform measure on [0,2/5]^2 for every pair of fronts. Then the probabilities that you win on 2, 3 and 4 fronts are 9/16, 6/16 and 1/16 respectively. Your expected margin of victory is -(9/16)+(6/16)+3*(1/16)=0, so you break even by Colonel Blotto rules. But you lose 9/16ths of the time by the rules of this game. $\endgroup$ Feb 23, 2010 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.