Complexity rises in multiplayer Blotto games with player-specific values
The Complexity of Multiplayer Colonel Blotto Games with Player-Specific Values
Computer Science and Game TheoryComputational Complexity
Summary
This paper looks at how hard it is to find stable strategies in a complex game where players allocate limited resources across battlefields. When only two players compete with the same values, finding these strategies is easier and fast. But when there are many players and each values battlefields differently, figuring out stable strategies becomes much harder. The authors prove that even small approximations of solutions are very difficult to compute in these multiplayer, personalized settings. However, for some simple cases with very limited resources, stable solutions can still be found efficiently.
What this means in practice
- •For game theory software developers: Understand the computational limits when designing software to find equilibria in complex multiplayer resource allocation games.
- •For algorithm designers: Avoid inefficient approaches for equilibrium computation in multiplayer games with player-specific valuations by using hardness results to guide algorithm design.
A theory result. No direct application yet.
Authors
Martin Bichler, Abheek Ghosh
Abstract
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 $(c/n)$-approximate Nash equilibrium is PPAD-hard for some constant $c>0$, even when every player has 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. 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 $\varepsilon$-approximate Nash equilibria for inverse-exponentially small $\varepsilon$. 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.