Solution
Blotto with an Edge
Show the problem again
Alice has 5 indivisible soldiers and Bob has 4. Each secretly distributes all of his or her soldiers over three battlefields (any non-negative integers summing to the total, zero allowed). On each battlefield, the side with more soldiers wins it and the other loses it; equal numbers is a draw. Alice's payoff is (battlefields she wins) − (battlefields she loses), and Bob's is the negative of that. With both sides playing optimally (mixed strategies allowed), what is the value of the game to Alice? Give a reduced fraction.
Worked solution
The answer is 1/2. This is a 21 × 15 zero-sum matrix game (21 ways to split 5 soldiers, 15 ways to split 4). Solving it as a linear program gives value 1/2: Alice has a mixed strategy that guarantees at least 1/2 on average against every Bob allocation, and Bob has one that holds her to at most 1/2 against every Alice allocation. One optimal strategy for Alice puts probability 1/6 on each of (0,2,3), (0,3,2), (2,2,1), (2,3,0) and 1/3 on (2,1,2). Conversely, Bob holds Alice to at most 1/2 by choosing, with probability 1/2 each, either a uniformly random arrangement of (0,2,2) or a uniformly random arrangement of (0,1,3); checking Alice's 21 allocations against this mix shows none averages more than 1/2. Since each side has a strategy certifying 1/2 from its own end, neither can do better, so the extra soldier is worth half a battlefield per game on average, and the value is 1/2.
Source: Colonel Blotto game (Borel, 1921); this 5-versus-4 instance written for AxiomIQ.