IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v35y2023i5p1143-1160.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Gabriele Dragotto & Rosario Scatamacchia, 2023. "The Zero Regrets Algorithm: Optimizing over Pure Nash Equilibria via Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1143-1160, September.
    • Handle: RePEc:inm:orijoc:v:35:y:2023:i:5:p:1143-1160
    DOI: 10.1287/ijoc.2022.0282
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.0282
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.0282?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Awi Federgruen & Ming Hu, 2015. "Multi-Product Price and Assortment Competition," Operations Research, INFORMS, vol. 63(3), pages 572-584, June.
    2. Harsanyi John C., 1995. "A New Theory of Equilibrium Selection for Games with Incomplete Information," Games and Economic Behavior, Elsevier, vol. 10(2), pages 318-332, August.
    3. Bernheim, B Douglas, 1984. "Rationalizable Strategic Behavior," Econometrica, Econometric Society, vol. 52(4), pages 1007-1028, July.
    4. C. Audet & S. Belhaiza & P. Hansen, 2006. "Enumeration of All the Extreme Equilibria in Game Theory: Bimatrix and Polymatrix Games," Journal of Optimization Theory and Applications, Springer, vol. 129(3), pages 349-372, June.
    5. Carvalho, Margarida & Lodi, Andrea & Pedroso, João.P., 2022. "Computing equilibria for integer programming games," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1057-1070.
    6. Porter, Ryan & Nudelman, Eugene & Shoham, Yoav, 2008. "Simple search methods for finding a Nash equilibrium," Games and Economic Behavior, Elsevier, vol. 63(2), pages 642-662, July.
    7. David Avis & Gabriel Rosenberg & Rahul Savani & Bernhard Stengel, 2010. "Enumeration of Nash equilibria for two-player games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 9-37, January.
    8. Edward Anderson & Bo Chen & Lusheng Shao, 2017. "Supplier Competition with Option Contracts for Discrete Blocks of Capacity," Operations Research, INFORMS, vol. 65(4), pages 952-967, August.
    9. Andrew McLennan, 2005. "The Expected Number of Nash Equilibria of a Normal Form Game," Econometrica, Econometric Society, vol. 73(1), pages 141-174, January.
    10. Steven Gabriel & Sauleh Siddiqui & Antonio Conejo & Carlos Ruiz, 2013. "Solving Discretely-Constrained Nash–Cournot Games with an Application to Power Markets," Networks and Spatial Economics, Springer, vol. 13(3), pages 307-326, September.
    11. Roughgarden, Tim & Tardos, Eva, 2004. "Bounding the inefficiency of equilibria in nonatomic congestion games," Games and Economic Behavior, Elsevier, vol. 47(2), pages 389-403, May.
    12. Pearce, David G, 1984. "Rationalizable Strategic Behavior and the Problem of Perfection," Econometrica, Econometric Society, vol. 52(4), pages 1029-1050, July.
    13. Matthias Köppe & Christopher Thomas Ryan & Maurice Queyranne, 2011. "Rational Generating Functions and Integer Programming Games," Operations Research, INFORMS, vol. 59(6), pages 1445-1460, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gabriele Dragotto & Amine Boukhtouta & Andrea Lodi & Mehdi Taobane, 2024. "The critical node game," Journal of Combinatorial Optimization, Springer, vol. 47(5), pages 1-20, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Pei, Ting & Takahashi, Satoru, 2019. "Rationalizable strategies in random games," Games and Economic Behavior, Elsevier, vol. 118(C), pages 110-125.
    2. Crönert, Tobias & Martin, Layla & Minner, Stefan & Tang, Christopher S., 2024. "Inverse optimization of integer programming games for parameter estimation arising from competitive retail location selection," European Journal of Operational Research, Elsevier, vol. 312(3), pages 938-953.
    3. Rui SILVA, 2018. "Equilibrium Selection in n-Person Static Games with Complete Information," Departmental Working Papers 2018-04, Department of Economics, Management and Quantitative Methods at Università degli Studi di Milano.
    4. Noga Alon & Kirill Rudov & Leeat Yariv, 2021. "Dominance Solvability in Random Games," Working Papers 2021-84, Princeton University. Economics Department..
    5. Cheng Guo & Merve Bodur & Joshua A. Taylor, 2021. "Copositive Duality for Discrete Markets and Games," Papers 2101.05379, arXiv.org, revised Jan 2021.
    6. Carvalho, Margarida & Lodi, Andrea & Pedroso, João.P., 2022. "Computing equilibria for integer programming games," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1057-1070.
    7. Vincent J. Vannetelbosch & P. Jean-Jacques Herings, 2000. "The equivalence of the Dekel-Fudenberg iterative procedure and weakly perfect rationalizability," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 15(3), pages 677-687.
    8. Ambrus, Attila, 2006. "Coalitional Rationalizability," Scholarly Articles 3200266, Harvard University Department of Economics.
    9. Dominiak, Adam & Lee, Dongwoo, 2023. "Testing rational hypotheses in signaling games," European Economic Review, Elsevier, vol. 160(C).
    10. Lawrence Christiano & Husnu Dalgic & Xiaoming Li, 2022. "Modelling the Great Recession as a Bank Panic: Challenges," Economica, London School of Economics and Political Science, vol. 89(S1), pages 200-238, June.
    11. Asheim, G.B. & Dufwenberg, M., 1996. "Admissibility and Common Knowledge," Discussion Paper 1996-16, Tilburg University, Center for Economic Research.
    12. Gilles Grandjean & Ana Mauleon & Vincent Vannetelbosch, 2017. "Strongly rational sets for normal-form games," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 5(1), pages 35-46, April.
    13. Jara-Moroni, Pedro, 2018. "Rationalizability and mixed strategies in large games," Economics Letters, Elsevier, vol. 162(C), pages 153-156.
    14. Choo, Lawrence C.Y & Kaplan, Todd R., 2014. "Explaining Behavior in the "11-20" Game," MPRA Paper 52808, University Library of Munich, Germany.
    15. Amanda Friedenberg & H. Jerome Keisler, 2021. "Iterated dominance revisited," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 72(2), pages 377-421, September.
    16. Alós-Ferrer, Carlos & Kuzmics, Christoph, 2013. "Hidden symmetries and focal points," Journal of Economic Theory, Elsevier, vol. 148(1), pages 226-258.
    17. Jacob K. Goeree & Charles A. Holt, 2001. "Ten Little Treasures of Game Theory and Ten Intuitive Contradictions," American Economic Review, American Economic Association, vol. 91(5), pages 1402-1422, December.
    18. Asheim, Geir B. & Dufwenberg, Martin, 2003. "Admissibility and common belief," Games and Economic Behavior, Elsevier, vol. 42(2), pages 208-234, February.
    19. Fabrizio Germano & Peio Zuazo-Garin, 2017. "Bounded rationality and correlated equilibria," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(3), pages 595-629, August.
    20. Abhijit Banerjee & Jörgen W. Weibull & Ken Binmore, 1996. "Evolution and Rationality: Some Recent Game-Theoretic Results," International Economic Association Series, in: Beth Allen (ed.), Economics in a Changing World, chapter 4, pages 90-117, Palgrave Macmillan.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:35:y:2023:i:5:p:1143-1160. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.