IDEAS home Printed from https://ideas.repec.org/a/spr/jogath/v53y2024i3d10.1007_s00182-024-00902-6.html
   My bibliography  Save this article

Semidefinite games

Author

Listed:
  • Constantin Ickstadt

    (Goethe-Universität)

  • Thorsten Theobald

    (Goethe-Universität)

  • Elias Tsigaridas

    (Sorbonne Université, Paris University, CNRS, and Inria Paris, IMJ-PRG)

Abstract

We introduce and study the class of semidefinite games, which generalizes bimatrix games and finite N-person games, by replacing the simplex of the mixed strategies for each player by a slice of the positive semidefinite cone in the space of real symmetric matrices. For semidefinite two-player zero-sum games, we show that the optimal strategies can be computed by semidefinite programming. Furthermore, we show that two-player semidefinite zero-sum games are almost equivalent to semidefinite programming, generalizing Dantzig’s result on the almost equivalence of bimatrix games and linear programming. For general two-player semidefinite games, we prove a spectrahedral characterization of the Nash equilibria. Moreover, we give constructions of semidefinite games with many Nash equilibria. In particular, we give a construction of semidefinite games whose number of connected components of Nash equilibria exceeds the long standing best known construction for many Nash equilibria in bimatrix games, which was presented by von Stengel in 1999.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jogath:v:53:y:2024:i:3:d:10.1007_s00182-024-00902-6
    DOI: 10.1007/s00182-024-00902-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00182-024-00902-6
    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/s00182-024-00902-6?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. Pahl, Lucas, 2023. "Polytope-form games and index/degree theories for extensive-form games," Games and Economic Behavior, Elsevier, vol. 141(C), pages 444-471.
    2. 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.
    3. Yang Cai & Ozan Candogan & Constantinos Daskalakis & Christos Papadimitriou, 2016. "Zero-Sum Polymatrix Games: A Generalization of Minmax," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 648-655, May.
    4. Predtetchinski, Arkadi, 2009. "A general structure theorem for the Nash equilibrium correspondence," Games and Economic Behavior, Elsevier, vol. 66(2), pages 950-958, July.
    5. Von Stengel, Bernhard, 2002. "Computing equilibria for two-person games," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 3, chapter 45, pages 1723-1759, Elsevier.
    6. 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.
    7. Ravi Kannan & Thorsten Theobald, 2010. "Games of fixed rank: a hierarchy of bimatrix games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 157-173, January.
    8. Miquel Oliu-Barton, 2021. "New Algorithms for Solving Zero-Sum Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 255-267, February.
    9. Lucas Pahl, 2022. "Polytope-form games and Index/Degree Theories for Extensive-form games," Papers 2201.02098, arXiv.org, revised Jul 2023.
    10. Bharat Adsul & Jugal Garg & Ruta Mehta & Milind Sohoni & Bernhard von Stengel, 2021. "Fast Algorithms for Rank-1 Bimatrix Games," Operations Research, INFORMS, vol. 69(2), pages 613-631, March.
    11. J. v. Neumann, 1945. "A Model of General Economic Equilibrium," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 13(1), pages 1-9.
    12. Ilan Adler, 2013. "The equivalence of linear programs and zero-sum games," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(1), pages 165-177, February.
    13. Borm, P.E.M. & Gijsberts, A. & Tijs, S.H., 1989. "A geometric-combinatorial approach to bimatrix games," Other publications TiSEM af7a280a-3e50-4bdf-b537-8, Tilburg University, School of Economics and Management.
    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. Bharat Adsul & Jugal Garg & Ruta Mehta & Milind Sohoni & Bernhard von Stengel, 2021. "Fast Algorithms for Rank-1 Bimatrix Games," Operations Research, INFORMS, vol. 69(2), pages 613-631, March.
    2. 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.
    3. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    4. Lucas Pahl & Carlos Pimienta, 2024. "Robust Equilibria in Generic Extensive form Games," Papers 2412.18449, arXiv.org, revised Mar 2025.
    5. Yiyin Cao & Yin Chen & Chuangyin Dang, 2024. "A Differentiable Path-Following Method with a Compact Formulation to Compute Proper Equilibria," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 377-396, March.
    6. Zacharias Bragoudakis & Evangelia Kasimati & Christos Pierros & Nikolaos Rodousakis & George Soklis, 2022. "Measuring Productivities for the 38 OECD Member Countries: An Input-Output Modelling Approach," Mathematics, MDPI, vol. 10(13), pages 1-21, July.
    7. Arthur Brackmann Netto, 2017. "The Double Edge of Case-Studies: A Frame-Based Definition of Economic Models," Working Papers, Department of Economics 2017_21, University of São Paulo (FEA-USP).
    8. Bernhard von Stengel & Antoon van den Elzen & Dolf Talman, 2002. "Computing Normal Form Perfect Equilibria for Extensive Two-Person Games," Econometrica, Econometric Society, vol. 70(2), pages 693-715, March.
    9. Csóka, Péter & Illés, Ferenc & Solymosi, Tamás, 2022. "On the Shapley value of liability games," European Journal of Operational Research, Elsevier, vol. 300(1), pages 378-386.
    10. Pham, Manh D. & Zelenyuk, Valentin, 2019. "Weak disposability in nonparametric production analysis: A new taxonomy of reference technology sets," European Journal of Operational Research, Elsevier, vol. 274(1), pages 186-198.
    11. Amir, Shmuel, 1995. "Welfare maximization in economic theory: Another viewpoint," Structural Change and Economic Dynamics, Elsevier, vol. 6(3), pages 359-376, August.
    12. Bogliacino, Francesco & Rampa, Giorgio, 2014. "Expectational bottlenecks and the emerging of new organizational forms," Structural Change and Economic Dynamics, Elsevier, vol. 29(C), pages 28-39.
    13. Fabrizio Germano, 2006. "On some geometry and equivalence classes of normal form games," International Journal of Game Theory, Springer;Game Theory Society, vol. 34(4), pages 561-581, November.
    14. Caspar Sauter, 2014. "How should we measure environmental policy stringency? A new approach," IRENE Working Papers 14-01, IRENE Institute of Economic Research.
    15. 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.
    16. Matheus Assaf, 2017. "Coast to Coast: How MIT's students linked the Solow model and optimal growth theory," Working Papers, Department of Economics 2017_20, University of São Paulo (FEA-USP).
    17. Heinz D. Kurz, 2011. "The Contributions of Two Eminent Japanese Scholars to the Development of Economic Theory: Michio Morishima and Takashi Negishi," Chapters, in: Heinz D. Kurz & Tamotsu Nishizawa & Keith Tribe (ed.), The Dissemination of Economic Ideas, chapter 13, Edward Elgar Publishing.
    18. Yannick Viossat, 2003. "Properties of Dual Reduction," Working Papers hal-00242992, HAL.
    19. Sickles, Robin C. & Song, Wonho & Zelenyuk, Valentin, 2018. "Econometric Analysis of Productivity: Theory and Implementation in R," Working Papers 18-008, Rice University, Department of Economics.
    20. Bade, Sophie & Haeringer, Guillaume & Renou, Ludovic, 2007. "More strategies, more Nash equilibria," Journal of Economic Theory, Elsevier, vol. 135(1), pages 551-557, July.

    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:spr:jogath:v:53:y:2024:i:3:d:10.1007_s00182-024-00902-6. 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.