The Zero Regrets Algorithm: Optimizing over Pure Nash Equilibria via Integer Programming

Gabriele Dragotto () and Rosario Scatamacchia ()
Additional contact information
Gabriele Dragotto: Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
Rosario Scatamacchia: Dipartimento di Ingegneria Gestionale e della Produzione, Politecnico di Torino, 10129 Torino, Italy

INFORMS Journal on Computing, 2023, vol. 35, issue 5, 1143-1160

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.

Keywords: integer programming games; algorithmic game theory; Nash equilibrium; mathematical programming games; integer programming (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0282 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:5:p:1143-1160

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().