Algorithm for Computing Approximate Nash Equilibrium in Continuous Games with Application to Continuous Blotto
This addresses a challenging problem in game theory for domains like national security and economics where actions are real-valued, though it appears incremental as it builds on existing finite-game algorithms.
The paper tackles the problem of computing Nash equilibrium in continuous games, which have infinite strategy spaces, by presenting a new algorithm that approximates equilibrium strategies for multiplayer and imperfect-information games, and demonstrates its effectiveness by quickly computing close approximations in a continuous Blotto game.
Successful algorithms have been developed for computing Nash equilibrium in a variety of finite game classes. However, solving continuous games -- in which the pure strategy space is (potentially uncountably) infinite -- is far more challenging. Nonetheless, many real-world domains have continuous action spaces, e.g., where actions refer to an amount of time, money, or other resource that is naturally modeled as being real-valued as opposed to integral. We present a new algorithm for {approximating} Nash equilibrium strategies in continuous games. In addition to two-player zero-sum games, our algorithm also applies to multiplayer games and games with imperfect information. We experiment with our algorithm on a continuous imperfect-information Blotto game, in which two players distribute resources over multiple battlefields. Blotto games have frequently been used to model national security scenarios and have also been applied to electoral competition and auction theory. Experiments show that our algorithm is able to quickly compute close approximations of Nash equilibrium strategies for this game.