Multiple oracle algorithm to solve continuous games
From MaRDI portal
Abstract: Continuous games are multiplayer games in which strategy sets are compact and utility functions are continuous. These games typically have a highly complicated structure of Nash equilibria, and numerical methods for the equilibrium computation are known only for particular classes of continuous games, such as two-player polynomial games or games in which pure equilibria are guaranteed to exist. This contribution focuses on the computation and approximation of a mixed strategy equilibrium for the whole class of multiplayer general-sum continuous games. We vastly extend the scope of applicability of the double oracle algorithm, initially designed and proved to converge only for two-player zero-sum games. Specifically, we propose an iterative strategy generation technique, which splits the original problem into the master problem with only a finite subset of strategies being considered, and the subproblem in which an oracle finds the best response of each player. This simple method is guaranteed to recover an approximate equilibrium in finitely many iterations. Further, we argue that the Wasserstein distance (the earth mover's distance) is the right metric for the space of mixed strategies for our purposes. Our main result is the convergence of this algorithm in the Wasserstein distance to an equilibrium of the original continuous game. The numerical experiments show the performance of our method on several classes of games including randomly generated examples.
Recommendations
- Algorithm for computing approximate Nash equilibrium in continuous games with application to continuous blotto
- Correlated equilibria in continuous games: characterization and computation
- An inverse-adjusted best response algorithm for Nash equilibria
- Separable and low-rank continuous games
- scientific article; zbMATH DE number 4043650
Cites work
- A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium Points
- A global Newton method to compute Nash equilibria.
- Algorithm for computing approximate Nash equilibrium in continuous games with application to continuous blotto
- An exact double-oracle algorithm for zero-sum extensive-form games with imperfect information
- An introduction to polynomial and semi-algebraic optimization
- An invitation to statistics in Wasserstein space
- Best response dynamics for continuous zero-sum games
- Complementarity problems in GAMS and the PATH solver
- Computational optimal transport. With applications to data sciences
- Computing Nash equilibria by iterated polymatrix approximation
- scientific article; zbMATH DE number 1243371 (Why is no real title available?)
- JuMP: a modeling language for mathematical optimization
- Learning in games with continuous action sets and unknown payoff functions
- Limit games and limit equilibria
- Nonlinear programming
- Note on unique Nash equilibrium in continuous games
- On Choosing and Bounding Probability Metrics
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
- Optimization with PDE Constraints
- Scalable Optimal Classifiers for Adversarial Settings Under Uncertainty
- Semidefinite programming for min-max problems and games
- Separable and low-rank continuous games
- Separable Network Games with Compact Strategy Sets
- The complexity of computing a Nash equilibrium
- Zero-sum polymatrix games: a generalization of minmax
Cited in
(1)
This page was built for publication: Multiple oracle algorithm to solve continuous games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6116849)
