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. 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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Predtetchinski, Arkadi, 2009. "A general structure theorem for the Nash equilibrium correspondence," Games and Economic Behavior, Elsevier, vol. 66(2), pages 950-958, July.
    9. Miquel Oliu-Barton, 2021. "New Algorithms for Solving Zero-Sum Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 255-267, February.
    10. Lucas Pahl, 2022. "Polytope-form games and Index/Degree Theories for Extensive-form games," Papers 2201.02098, arXiv.org, revised Jul 2023.
    11. 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.
    12. 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.
    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. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    2. Lucas Pahl & Carlos Pimienta, 2024. "Robust Equilibria in Generic Extensive form Games," Papers 2412.18449, arXiv.org, revised Mar 2025.
    3. Chen, Shun & Zhao, Xudong & Chen, Zhilong & Hou, Benwei & Wu, Yipeng, 2022. "A game-theoretic method to optimize allocation of defensive resource to protect urban water treatment plants against physical attacks," International Journal of Critical Infrastructure Protection, Elsevier, vol. 36(C).
    4. Yoann Verger, 2015. "Sraffa and ecological economics: review of the literature," Working Papers hal-01182894, HAL.
    5. 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.
    6. Palma, Nuno, 2018. "Money and modernization in early modern England," Financial History Review, Cambridge University Press, vol. 25(3), pages 231-261, December.
    7. Jean-Luc Gaffard, 2022. "Instabilité et résilience des économies de marché: Essai sur l'économie du libéralisme social," GREDEG Working Papers 2022-33, Groupe de REcherche en Droit, Economie, Gestion (GREDEG CNRS), Université Côte d'Azur, France.
    8. 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).
    9. Eduardo Ley, 1991. "Eficiencia productiva: un estudio aplicado al sector hospitalario," Investigaciones Economicas, Fundación SEPI, vol. 15(1), pages 71-88, January.
    10. Hazan, Aurélien, 2017. "Volume of the steady-state space of financial flows in a monetary stock-flow-consistent model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 473(C), pages 589-602.
    11. 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.
    12. 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.
    13. Amir, Shmuel, 1995. "Welfare maximization in economic theory: Another viewpoint," Structural Change and Economic Dynamics, Elsevier, vol. 6(3), pages 359-376, August.
    14. 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.
    15. Giuseppe Freni & Fausto Gozzi & Neri Salvadori, 2017. "Existence of optimal strategies in linear multisector models with several consumption goods," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 40(1), pages 199-229, November.
    16. Michel Truchon, 1988. "Programmation mathématique et théorie économique," L'Actualité Economique, Société Canadienne de Science Economique, vol. 64(2), pages 143-156.
    17. Cem Ertur & Wilfried Koch, 2006. "The Role of Human Capital and Technological Interdependence in Growth and Convergence Processes: International Evidence," DEGIT Conference Papers c011_029, DEGIT, Dynamics, Economic Growth, and International Trade.
    18. Nayak, Purusottam & Mishra, SK, 2009. "Structural Change in Meghalaya: Theory and Evidence," MPRA Paper 15728, University Library of Munich, Germany.
    19. Caspar Sauter, 2014. "How should we measure environmental policy stringency? A new approach," IRENE Working Papers 14-01, IRENE Institute of Economic Research.
    20. 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).

    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.