IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v303y2022i3p1057-1070.html

Computing equilibria for integer programming games

Author

Listed:
  • Carvalho, Margarida
  • Lodi, Andrea
  • Pedroso, João.P.

Abstract

The recently-defined class of integer programming games (IPG) models situations where multiple self-interested decision makers interact, with their strategy sets represented by a finite set of linear constraints together with integer requirements. Many real-world problems can suitably be cast in this way, hence anticipating IPG outcomes is of crucial value for policy makers. Nash equilibria have been widely accepted as the solution concept of a game. Thus, their computation provides a reasonable prediction of games outcome.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:303:y:2022:i:3:p:1057-1070
    DOI: 10.1016/j.ejor.2022.03.048
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722002727
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.03.048?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
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. Gerhard J. Woeginger, 2021. "The trouble with the second quantifier," 4OR, Springer, vol. 19(2), pages 157-181, June.
    3. 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.
    4. Carvalho, Margarida & Pedroso, João Pedro & Telha, Claudio & Van Vyve, Mathieu, 2018. "Competitive uncapacitated lot-sizing game," International Journal of Production Economics, Elsevier, vol. 204(C), pages 148-159.
    5. 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.
    6. McLennan, Andrew & Berg, Johannes, 2005. "Asymptotic expected number of Nash equilibria of two-player normal form games," Games and Economic Behavior, Elsevier, vol. 51(2), pages 264-295, May.
    7. Noah Stein & Asuman Ozdaglar & Pablo Parrilo, 2008. "Separable and low-rank continuous games," International Journal of Game Theory, Springer;Game Theory Society, vol. 37(4), pages 475-504, December.
    8. Robert J. Aumann, 2025. "Subjectivity and Correlation in Randomized Strategies," World Scientific Book Chapters, in: SELECTED CONTRIBUTIONS TO GAME THEORY, chapter 4, pages 73-113, World Scientific Publishing Co. Pte. Ltd..
    9. Robert J. Aumann, 2025. "Correlated Equilibrium as an Expression of Bayesian Rationality," World Scientific Book Chapters, in: SELECTED CONTRIBUTIONS TO GAME THEORY, chapter 7, pages 175-200, World Scientific Publishing Co. Pte. Ltd..
    10. P. C. Gilmore & R. E. Gomory, 1961. "A Linear Programming Approach to the Cutting-Stock Problem," Operations Research, INFORMS, vol. 9(6), pages 849-859, December.
    11. Constantino, Miguel & Klimentova, Xenia & Viana, Ana & Rais, Abdur, 2013. "New insights on integer-programming models for the kidney exchange problem," European Journal of Operational Research, Elsevier, vol. 231(1), pages 57-68.
    12. Huppmann, Daniel & Siddiqui, Sauleh, 2018. "An exact solution method for binary equilibrium problems with compensation and the power market uplift problem," European Journal of Operational Research, Elsevier, vol. 266(2), pages 622-638.
    13. Li, Hongyan & Meissner, Joern, 2011. "Competition under capacitated dynamic lot-sizing with capacity acquisition," International Journal of Production Economics, Elsevier, vol. 131(2), pages 535-544, June.
    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. Pengli Mo & Zhiyuan Liu & Zhijia Tan & Wen Yi & Pan Liu, 2024. "Subsidy Allocation Problem with Bus Frequency Setting Game: A Trilevel Formulation and Exact Algorithm," Transportation Science, INFORMS, vol. 58(3), pages 639-663, May.
    2. Claudio Telha & Margarida Carvalho, 2025. "Integration of Sales and Operations: A Dynamic Mixed-Integer Programming Game," Dynamic Games and Applications, Springer, vol. 15(1), pages 306-328, March.
    3. Lindong Liu & Xiangtong Qi & Zhou Xu, 2024. "Stabilizing Grand Cooperation via Cost Adjustment: An Inverse Optimization Approach," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 635-656, March.
    4. 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.
    5. Blom, Danny & Smeulders, Bart & Spieksma, Frits, 2024. "Rejection-proof mechanisms for multi-agent kidney exchange," Games and Economic Behavior, Elsevier, vol. 143(C), pages 25-50.
    6. Lucky Cho & Thomas C. Sharkey, 2023. "Integer Programming Methods to Identify Nash Equilibrium Solutions for Platform-Based Scheduling Games," SN Operations Research Forum, Springer, vol. 4(4), pages 1-27, December.
    7. Stefan Schwarze & Oliver Stein, 2023. "A branch-and-prune algorithm for discrete Nash equilibrium problems," Computational Optimization and Applications, Springer, vol. 86(2), pages 491-519, November.
    8. Margarida Carvalho & Gabriele Dragotto & Andrea Lodi & Sriram Sankaranarayanan, 2026. "The Cut-and-Play Algorithm: Computing Nash Equilibria via Outer Approximations," Operations Research, INFORMS, vol. 74(2), pages 1070-1086, March.
    9. Tobias Crönert & Stefan Minner, 2024. "Equilibrium Identification and Selection in Finite Games," Operations Research, INFORMS, vol. 72(2), pages 816-831, March.
    10. 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.
    11. Pierre, Cayet & Catherine, Azzaro-Pantel & Sylvain, Bourjade & Catherine, Muller-Vibes, 2024. "Beyond the “bottom-up” and “top-down” controversy: A methodological inquiry into hybrid modeling methods for hydrogen supply chains," International Journal of Production Economics, Elsevier, vol. 268(C).
    12. Amin Dehghanian & Yujia Xie & Nicoleta Serban, 2024. "Identifying Socially Optimal Equilibria Using Combinatorial Properties of Nash Equilibria in Bimatrix Games," INFORMS Journal on Computing, INFORMS, vol. 36(5), pages 1261-1286, September.
    13. Margarida Carvalho & Gabriele Dragotto & Felipe Feijoo & Andrea Lodi & Sriram Sankaranarayanan, 2024. "When Nash Meets Stackelberg," Management Science, INFORMS, vol. 70(10), pages 7308-7324, October.

    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. Amin Dehghanian & Yujia Xie & Nicoleta Serban, 2024. "Identifying Socially Optimal Equilibria Using Combinatorial Properties of Nash Equilibria in Bimatrix Games," INFORMS Journal on Computing, INFORMS, vol. 36(5), pages 1261-1286, September.
    2. Margarida Carvalho & Gabriele Dragotto & Andrea Lodi & Sriram Sankaranarayanan, 2026. "The Cut-and-Play Algorithm: Computing Nash Equilibria via Outer Approximations," Operations Research, INFORMS, vol. 74(2), pages 1070-1086, March.
    3. Stein, Noah D. & Parrilo, Pablo A. & Ozdaglar, Asuman, 2011. "Correlated equilibria in continuous games: Characterization and computation," Games and Economic Behavior, Elsevier, vol. 71(2), pages 436-455, March.
    4. Tobias Crönert & Stefan Minner, 2024. "Equilibrium Identification and Selection in Finite Games," Operations Research, INFORMS, vol. 72(2), pages 816-831, March.
    5. Claudio Telha & Margarida Carvalho, 2025. "Integration of Sales and Operations: A Dynamic Mixed-Integer Programming Game," Dynamic Games and Applications, Springer, vol. 15(1), pages 306-328, March.
    6. Margarida Carvalho & Gabriele Dragotto & Felipe Feijoo & Andrea Lodi & Sriram Sankaranarayanan, 2024. "When Nash Meets Stackelberg," Management Science, INFORMS, vol. 70(10), pages 7308-7324, October.
    7. 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.
    8. Dirk Bergemann & Stephen Morris, 2019. "Information Design: A Unified Perspective," Journal of Economic Literature, American Economic Association, vol. 57(1), pages 44-95, March.
    9. Konstantinos Georgalos & Indrajit Ray & Sonali SenGupta, 2020. "Nash versus coarse correlation," Experimental Economics, Springer;Economic Science Association, vol. 23(4), pages 1178-1204, December.
    10. Antonio Cabrales & Michalis Drouvelis & Zeynep Gurguy & Indrajit Ray, 2017. "Transparency is Overrated: Communicating in a Coordination Game with Private Information," CESifo Working Paper Series 6781, CESifo.
    11. Chirantan Ganguly & Indrajit Ray, 2023. "Simple Mediation in a Cheap-Talk Game," Games, MDPI, vol. 14(3), pages 1-14, June.
    12. Robert Nau, 2001. "De Finetti was Right: Probability Does Not Exist," Theory and Decision, Springer, vol. 51(2), pages 89-124, December.
    13. Ehud Lehrer & Eilon Solan, 2007. "Learning to play partially-specified equilibrium," Levine's Working Paper Archive 122247000000001436, David K. Levine.
    14. Lenzo, Justin & Sarver, Todd, 2006. "Correlated equilibrium in evolutionary models with subpopulations," Games and Economic Behavior, Elsevier, vol. 56(2), pages 271-284, August.
    15. Vitaly Pruzhansky, 2004. "A Discussion of Maximin," Tinbergen Institute Discussion Papers 04-028/1, Tinbergen Institute.
    16. Hendrik Vollmer, 2013. "What kind of game is everyday interaction?," Rationality and Society, , vol. 25(3), pages 370-404, August.
    17. Tommaso Denti & Doron Ravid, 2023. "Robust Predictions in Games with Rational Inattention," Papers 2306.09964, arXiv.org.
    18. repec:dau:papers:123456789/8159 is not listed on IDEAS
    19. Michael Suk-Young Chwe, 1998. "Culture, Circles, And Commercials," Rationality and Society, , vol. 10(1), pages 47-75, February.
    20. Shmuel Zamir, 2008. "Bayesian games: Games with incomplete information," Discussion Paper Series dp486, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    21. Cédric Wanko, 2008. "Approche Conceptuelle et Algorithmique des Equilibres de Nash Robustes Incitatifs," Working Papers 08-03, LAMETA, Universtiy of Montpellier, revised Feb 2008.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:eee:ejores:v:303:y:2022:i:3:p:1057-1070. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.