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 search 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. 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.
    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. Miquel Oliu-Barton, 2021. "New Algorithms for Solving Zero-Sum Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 255-267, February.
    8. Lucas Pahl, 2022. "Polytope-form games and Index/Degree Theories for Extensive-form games," Papers 2201.02098, arXiv.org, revised Jul 2023.
    9. 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.
    10. 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.
    11. 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.
    12. 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. 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.
    3. 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.
    4. 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).
    5. 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.
    6. 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.
    7. Amir, Shmuel, 1995. "Welfare maximization in economic theory: Another viewpoint," Structural Change and Economic Dynamics, Elsevier, vol. 6(3), pages 359-376, August.
    8. 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.
    9. Caspar Sauter, 2014. "How should we measure environmental policy stringency? A new approach," IRENE Working Papers 14-01, IRENE Institute of Economic Research.
    10. 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).
    11. 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.
    12. 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.
    13. Noah Stein & Asuman Ozdaglar & Pablo Parrilo, 2011. "Structure of extreme correlated equilibria: a zero-sum example and its implications," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(4), pages 749-767, November.
    14. Grüne, Lars & Semmler, Willi & Stieler, Marleen, 2015. "Using nonlinear model predictive control for dynamic decision problems in economics," Journal of Economic Dynamics and Control, Elsevier, vol. 60(C), pages 112-133.
    15. Winkler, Ralph, 2006. "Valuation of ecosystem goods and services: Part 1: An integrated dynamic approach," Ecological Economics, Elsevier, vol. 59(1), pages 82-93, August.
    16. Boldrin, Michele & Levine, David K., 2008. "Perfectly competitive innovation," Journal of Monetary Economics, Elsevier, vol. 55(3), pages 435-453, April.
    17. Mabid Ali al-Jarhi, 1985. "Towards an Islamic Macro Model of Distribution: A Comparative Approach نحو نموذج ماكرو إسلامي للتوزيع: مقاربة مقارنة," Journal of Research in Islamic Economics, King Abdulaziz University, Islamic Economics Institute., vol. 2(2), pages 3-29, January.
    18. Ilan Adler & Martin Bullinger & Vijay V. Vazirani, 2024. "A Generalization of von Neumann's Reduction from the Assignment Problem to Zero-Sum Games," Papers 2410.10767, arXiv.org.
    19. repec:hal:spmain:info:hdl:2441/4eus3ho3fk813p8qcqfc1gaft2 is not listed on IDEAS
    20. Valizadeh, Mehrdad & Gohari, Amin, 2019. "Playing games with bounded entropy," Games and Economic Behavior, Elsevier, vol. 115(C), pages 363-380.
    21. K. Vela Velupillai, 2011. "The Fundamental Theorems of Welfare Economics, DSGE and the Theory of Policy - Computable & Constructive Foundations," ASSRU Discussion Papers 1125, ASSRU - Algorithmic Social Science Research Unit.

    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.