The Complexity of Multiplayer Colonel Blotto Games with Player-Specific Values
In the authors' words
We study equilibrium computation in discrete multiplayer Colonel Blotto games with player-specific battlefield values. In the two-player model with common battlefield values, equilibria can be computed in polynomial time. We show that this tractability breaks down in the multiplayer model with player-specific values under the standard uniform tie-breaking rule. In particular, computing a -approximate Nash equilibrium is PPAD-hard for some constant , even when every player has three resources, where is the number of players. The main technical step is PPAD-hardness for computing a constant-approximate well-supported Nash equilibrium. In contrast, under uniform tie-breaking, a pure Nash equilibrium can be computed in polynomial time when every player has one resource. We also prove PPAD membership for computing -approximate Nash equilibria for inverse-exponentially small . Finally, for non-uniform monotone tie-breaking, we show PPAD-hardness even when every player has one resource and all players have identical battlefield values.
Appeared: Friday, September 25. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 64 pages, 3 figures