No Perfect Strategy Exists for Splitting Your Budget Across Many Rivals

Researchers studying equilibrium computation in discrete multiplayer Colonel Blotto games with player-specific battlefield values report a sharp divide. In the two-player model with common battlefield values, equilibria can be computed in polynomial time. But in the multiplayer model with player-specific values under the standard uniform tie-breaking rule, computing a (c/n)-approximate Nash equilibrium is PPAD-hard for some constant c > 0 — even when every player has just three resources, where n is the number of players. The main technical step is PPAD-hardness for computing a constant-approximate well-supported Nash equilibrium. By contrast, under uniform tie-breaking, a pure Nash equilibrium can be computed in polynomial time when every player has one resource. The authors also prove PPAD membership for computing ε-approximate Nash equilibria for inverse-exponentially small ε. Finally, for non-uniform monotone tie-breaking, they show PPAD-hardness even when every player has one resource and all players have identical battlefield values.