IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v86y2023i2d10.1007_s10589-023-00500-4.html
   My bibliography  Save this article

A branch-and-prune algorithm for discrete Nash equilibrium problems

Author

Listed:
  • Stefan Schwarze

    (Institute for Operations Research (IOR), Karlsruhe Institute of Technology (KIT))

  • Oliver Stein

    (Institute for Operations Research (IOR), Karlsruhe Institute of Technology (KIT))

Abstract

We present a branch-and-prune procedure for discrete Nash equilibrium problems with a convex description of each player’s strategy set. The derived pruning criterion does not require player convexity, but only strict convexity of some player’s objective function in a single variable. If satisfied, it prunes choices for this variable by stating activity of certain constraints. This results in a synchronous branching and pruning method. An algorithmic implementation and numerical tests are presented for randomly generated instances with convex polyhedral strategy sets and convex quadratic as well as non-convex quadratic objective functions.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:coopap:v:86:y:2023:i:2:d:10.1007_s10589-023-00500-4
    DOI: 10.1007/s10589-023-00500-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-023-00500-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10589-023-00500-4?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 search for a different version of it.

    References listed on IDEAS

    as
    1. Axel Dreves & Christian Kanzow & Oliver Stein, 2012. "Nonsmooth optimization reformulations of player convex generalized Nash equilibrium problems," Journal of Global Optimization, Springer, vol. 53(4), pages 587-614, August.
    2. 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.
    3. Francisco Facchinei & Veronica Piccialli & Marco Sciandrone, 2011. "Decomposition algorithms for generalized potential games," Computational Optimization and Applications, Springer, vol. 50(2), pages 237-262, October.
    4. 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)

    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. 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.
    2. Simone Sagratella, 2017. "Algorithms for generalized potential games with mixed-integer variables," Computational Optimization and Applications, Springer, vol. 68(3), pages 689-717, December.
    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. Sagratella, Simone & Schmidt, Marcel & Sudermann-Merx, Nathan, 2020. "The noncooperative fixed charge transportation problem," European Journal of Operational Research, Elsevier, vol. 284(1), pages 373-382.
    5. Oliver Stein & Nathan Sudermann-Merx, 2016. "The Cone Condition and Nonsmoothness in Linear Generalized Nash Games," Journal of Optimization Theory and Applications, Springer, vol. 170(2), pages 687-709, August.
    6. Nadja Harms & Tim Hoheisel & Christian Kanzow, 2015. "On a Smooth Dual Gap Function for a Class of Player Convex Generalized Nash Equilibrium Problems," Journal of Optimization Theory and Applications, Springer, vol. 166(2), pages 659-685, August.
    7. Jiang, Zhoutong & Lei, Chao & Ouyang, Yanfeng, 2020. "Optimal investment and management of shared bikes in a competitive market," Transportation Research Part B: Methodological, Elsevier, vol. 135(C), pages 143-155.
    8. Migot, Tangi & Cojocaru, Monica-G., 2020. "A parametrized variational inequality approach to track the solution set of a generalized nash equilibrium problem," European Journal of Operational Research, Elsevier, vol. 283(3), pages 1136-1147.
    9. Le Cadre, Hélène & Mou, Yuting & Höschle, Hanspeter, 2022. "Parametrized Inexact-ADMM based coordination games: A normalized Nash equilibrium approach," European Journal of Operational Research, Elsevier, vol. 296(2), pages 696-716.
    10. Hu, Shu & Fu, Ke & Wu, Tong, 2021. "The role of consumer behavior and power structures in coping with shoddy goods," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 155(C).
    11. J. Atsu Amegashie, 2020. "Citations And Incentives In Academic Contests," Economic Inquiry, Western Economic Association International, vol. 58(3), pages 1233-1244, July.
    12. Didier Aussel & Simone Sagratella, 2017. "Sufficient conditions to compute any solution of a quasivariational inequality via a variational inequality," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 85(1), pages 3-18, February.
    13. Hélène Le Cadre & Yuting Mou & Hanspeter Höschle, 2020. "Parametrized Inexact-ADMM to Span the Set of Generalized Nash Equilibria: A Normalized Equilibrium Approach," Working Papers hal-02925005, HAL.
    14. Simone Sagratella, 2017. "Computing equilibria of Cournot oligopoly models with mixed-integer quantities," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 86(3), pages 549-565, December.
    15. Julio B. Clempner, 2021. "A Proximal/Gradient Approach for Computing the Nash Equilibrium in Controllable Markov Games," Journal of Optimization Theory and Applications, Springer, vol. 188(3), pages 847-862, March.
    16. Jinlong Lei & Uday V. Shanbhag, 2020. "Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization," Operations Research, INFORMS, vol. 68(6), pages 1742-1766, November.
    17. Jiawang Nie & Xindong Tang & Lingling Xu, 2021. "The Gauss–Seidel method for generalized Nash equilibrium problems of polynomials," Computational Optimization and Applications, Springer, vol. 78(2), pages 529-557, March.
    18. Didier Aussel & Asrifa Sultana & Vellaichamy Vetrivel, 2016. "On the Existence of Projected Solutions of Quasi-Variational Inequalities and Generalized Nash Equilibrium Problems," Journal of Optimization Theory and Applications, Springer, vol. 170(3), pages 818-837, September.
    19. Jacquot, Paulin & Wan, Cheng, 2022. "Nonatomic aggregative games with infinitely many types," European Journal of Operational Research, Elsevier, vol. 301(3), pages 1149-1165.
    20. Axel Dreves & Simone Sagratella, 2020. "Nonsingularity and Stationarity Results for Quasi-Variational Inequalities," Journal of Optimization Theory and Applications, Springer, vol. 185(3), pages 711-743, June.

    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:spr:coopap:v:86:y:2023:i:2:d:10.1007_s10589-023-00500-4. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.