IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v49y2024i2p1065-1090.html

Nash Equilibrium Problems of Polynomials

Author

Listed:
  • Jiawang Nie

    (Department of Mathematics, University of California San Diego, La Jolla, California 92093)

  • Xindong Tang

    (Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong)

Abstract

This paper studies Nash equilibrium problems that are given by polynomial functions. We formulate efficient polynomial optimization problems for computing Nash equilibria. The Moment-sum-of-squares relaxations are used to solve them. Under generic assumptions, the method can find a Nash equilibrium, if there is one. Moreover, it can find all Nash equilibria if there are finitely many ones of them. The method can also detect nonexistence if there is no Nash equilibrium.

Suggested Citation

  • Jiawang Nie & Xindong Tang, 2024. "Nash Equilibrium Problems of Polynomials," Mathematics of Operations Research, INFORMS, vol. 49(2), pages 1065-1090, May.
    • Handle: RePEc:inm:ormoor:v:49:y:2024:i:2:p:1065-1090
    DOI: 10.1287/moor.2022.0334
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.0334
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.0334?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. 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.
    2. Jiawang Nie & Xinzhen Zhang, 2018. "Real eigenvalues of nonsymmetric tensors," Computational Optimization and Applications, Springer, vol. 70(1), pages 1-32, May.
    3. Breton, Michele & Zaccour, Georges & Zahaf, Mehdi, 2006. "A game-theoretic formulation of joint implementation of environmental projects," European Journal of Operational Research, Elsevier, vol. 168(1), pages 221-239, January.
    4. Francisco Facchinei & Christian Kanzow, 2010. "Generalized Nash Equilibrium Problems," Annals of Operations Research, Springer, vol. 175(1), pages 177-211, March.
    5. Ruchira Datta, 2010. "Finding all Nash equilibria of a finite game using polynomial algebra," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 55-96, January.
    6. Jiawang Nie, 2011. "Polynomial Matrix Inequality and Semidefinite Representation," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 398-415, August.
    7. Eleftherios Couzoudis & Philipp Renner, 2013. "Computing generalized Nash equilibria by polynomial programming," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 77(3), pages 459-472, June.
    8. Amir Ali Ahmadi & Jeffrey Zhang, 2021. "Semidefinite Programming and Nash Equilibria in Bimatrix Games," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 607-628, May.
    9. 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.
    10. Eric Maskin, 1999. "Nash Equilibrium and Welfare Optimality," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 66(1), pages 23-38.
    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. 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.
    2. Rehbeck, John, 2018. "Note on unique Nash equilibrium in continuous games," Games and Economic Behavior, Elsevier, vol. 110(C), pages 216-225.
    3. 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.
    4. Abhishek Singh & Debdas Ghosh & Qamrul Hasan Ansari, 2024. "Inexact Newton Method for Solving Generalized Nash Equilibrium Problems," Journal of Optimization Theory and Applications, Springer, vol. 201(3), pages 1333-1363, June.
    5. Yann BRAOUEZEC & Keyvan KIANI, 2021. "Economic foundations of generalized games with shared constraint: Do binding agreements lead to less Nash equilibria?," Working Papers 2021-ACF-06, IESEG School of Management.
    6. Han, Deren & Zhang, Hongchao & Qian, Gang & Xu, Lingling, 2012. "An improved two-step method for solving generalized Nash equilibrium problems," European Journal of Operational Research, Elsevier, vol. 216(3), pages 613-623.
    7. Constantin Ickstadt & Thorsten Theobald & Elias Tsigaridas, 2024. "Semidefinite games," International Journal of Game Theory, Springer;Game Theory Society, vol. 53(3), pages 827-857, September.
    8. Jiawang Nie & Zi Yang, 2024. "The Multi-Objective Polynomial Optimization," Mathematics of Operations Research, INFORMS, vol. 49(4), pages 2723-2748, November.
    9. Yann Braouezec & Keyvan Kiani, 2023. "Economic foundations of generalized games with shared constraint: Do binding agreements lead to less Nash equilibria?," Post-Print hal-03967955, HAL.
    10. Braouezec, Yann & Kiani, Keyvan, 2023. "Economic foundations of generalized games with shared constraint: Do binding agreements lead to less Nash equilibria?," European Journal of Operational Research, Elsevier, vol. 308(1), pages 467-479.
    11. Rodica Ioana Lung & Noémi Gaskó & Mihai Alexandru Suciu, 2020. "Pareto-based evolutionary multiobjective approaches and the generalized Nash equilibrium problem," Journal of Heuristics, Springer, vol. 26(4), pages 561-584, August.
    12. Margarita Kirneva & Matias Nunez, 2021. "Voting by Simultaneous Vetoes," Working Papers 2021-08, Center for Research in Economics and Statistics.
    13. 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.
    14. Lombardi, Michele & Yoshihara, Naoki, 2016. "Partially-honest Nash Implementation with Non-connected Honesty Standards," Discussion Paper Series 633, Institute of Economic Research, Hitotsubashi University.
    15. Mezzetti, Claudio & Renou, Ludovic, 2012. "Implementation in mixed Nash equilibrium," Journal of Economic Theory, Elsevier, vol. 147(6), pages 2357-2375.
    16. Dubey, Pradeep & Sondermann, Dieter, 2009. "Perfect competition in an oligopoly (including bilateral monopoly)," Games and Economic Behavior, Elsevier, vol. 65(1), pages 124-141, January.
    17. Hitoshi Matsushima & Shunya Noda, 2020. "Mechanism Design with Blockchain Enforcement," DSSR Discussion Papers 111, Graduate School of Economics and Management, Tohoku University.
    18. Núñez, Matías & Laslier, Jean-François, 2015. "Bargaining through Approval," Journal of Mathematical Economics, Elsevier, vol. 60(C), pages 63-73.
    19. Salvador Barberà & Dolors Berga & Bernardo Moreno & Antonio Nicolò, 2025. "Condorcet Consistency And Pairwise Justifiability Under Variable Agendas," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 66(1), pages 313-329, February.
    20. Yi, Jianxin, 2012. "Double implementation in Nash and M-Nash equilibria," Economics Letters, Elsevier, vol. 116(1), pages 105-107.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    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:inm:ormoor:v:49:y:2024:i:2:p:1065-1090. 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.