The Zero Regrets Algorithm: Optimizing over Pure Nash Equilibria via Integer Programming
From MaRDI portal
Abstract: Designing efficient algorithms to compute Nash equilibria poses considerable challenges in Algorithmic Game Theory and Optimization. In this work, we employ integer programming techniques to compute Nash equilibria in Integer Programming Games, a class of simultaneous and non-cooperative games where each player solves a parametrized integer program. We introduce ZERO Regrets, a general and efficient cutting plane algorithm to compute, enumerate, and select Nash equilibria. Our framework leverages the concept of equilibrium inequality, an inequality valid for any Nash equilibrium, and the associated equilibrium separation oracle. We evaluate our algorithmic framework on a wide range of practical and methodological problems from the literature, providing a solid benchmark against the existing approaches.
Recommendations
- Computing equilibria for integer programming games
- Computing Nash equilibria by iterated polymatrix approximation
- A mixed 0-1 linear programming approach to the computation of all pure-strategy Nash equilibria of a finite \(n\)-person game in normal form
- Computing exact and approximate Nash equilibria in 2-player games
Cited in
(5)- Computing equilibria for integer programming games
- Integer programming methods to identify Nash equilibrium solutions for platform-based scheduling games
- The critical node game
- Generalized Nash equilibrium problems with mixed-integer variables
- Computing approximate Nash equilibria for integer programming games
This page was built for publication: The Zero Regrets Algorithm: Optimizing over Pure Nash Equilibria via Integer Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6200147)
