Algorithm for computing approximate Nash equilibrium in continuous games with application to continuous blotto

DOI10.3390/G12020047MaRDI QIDQ2052549zbMATH OpenOpenAlexFDO

Authors Sam Ganzfried

Publication date 26 November 2021

Published in Games (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2006.07443

zbMATH Keywords

Blotto gamecontinuous gameimperfect informationnational security

Mathematics Subject Classification ID

2-person games (91A05) Noncooperative games (91A10) Algorithmic game theory and complexity (91A68)

Abstract: 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.

Review text

Summary: 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.

Recommendations

• From duels to battlefields: computing equilibria of Blotto and other games
• scientific article; zbMATH DE number 1908200
• An inverse-adjusted best response algorithm for Nash equilibria
• The multiplayer Colonel Blotto game
• Computing Nash equilibria by iterated polymatrix approximation

Cites work

• A Blotto game with incomplete information
• A Blotto game with multi-dimensional incomplete information
• A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium Points
• An iterative method of solving a game
• Computing pure Bayesian-Nash equilibria in games with finite actions and continuous types
• Discrete Colonel Blotto and general lotto games
• First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
• From duels to battlefields: computing equilibria of Blotto and other games
• Game theory
• scientific article; zbMATH DE number 1233801 (Why is no real title available?)
• scientific article; zbMATH DE number 3069635 (Why is no real title available?)
• scientific article; zbMATH DE number 3078991 (Why is no real title available?)
• Non-cooperative games
• Separable and low-rank continuous games
• Superhuman AI for multiplayer poker
• The Colonel Blotto game
• The complexity of computing a Nash equilibrium

Cited in

(5)

• \(N\)-dimensional Blotto game with heterogeneous battlefield values
• A preface for the special issue ``economics of conflict and terrorism
• Toward the Nash equilibrium solutions for large-scale pentagonal fuzzy continuous static games
• On Stackelberg leader with min-max followers to solve fuzzy continuous static games
• Multiple oracle algorithm to solve continuous games

Describes a project that uses

Uses Software

• Gurobi
• Pluribus

This page was built for publication: Algorithm for computing approximate Nash equilibrium in continuous games with application to continuous blotto

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052549)