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 noncooperative games in which each player solves a parameterized 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.
The Zero Regrets Algorithm: Optimizing over Pure Nash Equilibria via Integer Programming / Dragotto, G.; Scatamacchia, R.. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 35:5(2023), pp. 1143-1160. [10.1287/ijoc.2022.0282]
The Zero Regrets Algorithm: Optimizing over Pure Nash Equilibria via Integer Programming
Scatamacchia R.
2023
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 noncooperative games in which each player solves a parameterized 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.File | Dimensione | Formato | |
---|---|---|---|
dragotto-scatamacchia-2023-the-zero-regrets-algorithm-optimizing-over-pure-nash-equilibria-via-integer-programming.pdf
accesso riservato
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Non Pubblico - Accesso privato/ristretto
Dimensione
3.01 MB
Formato
Adobe PDF
|
3.01 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
2111.06382v4.pdf
accesso aperto
Tipologia:
1. Preprint / submitted version [pre- review]
Licenza:
Pubblico - Tutti i diritti riservati
Dimensione
434.15 kB
Formato
Adobe PDF
|
434.15 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2989902