Semidefinite games

Constantin Ickstadt, Thorsten Theobald () and Elias Tsigaridas
Additional contact information
Constantin Ickstadt: Goethe-Universität
Thorsten Theobald: Goethe-Universität
Elias Tsigaridas: Sorbonne Université, Paris University, CNRS, and Inria Paris, IMJ-PRG

International Journal of Game Theory, 2024, vol. 53, issue 3, No 5, 827-857

Abstract: 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.

Keywords: Semidefinite games; Bimatrix games; Nash equilibrium; Dantzig game; Number of Nash equilibria; Semidefinite programming (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-024-00902-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:53:y:2024:i:3:d:10.1007_s00182-024-00902-6

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-024-00902-6

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().