Semidefinite Programming and Nash Equilibria in Bimatrix Games

Amir Ali Ahmadi () and Jeffrey Zhang ()
Additional contact information
Amir Ali Ahmadi: Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
Jeffrey Zhang: Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544

INFORMS Journal on Computing, 2021, vol. 33, issue 2, 607-628

Abstract: We explore the power of semidefinite programming (SDP) for finding additive ɛ-approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic programming formulation of the Nash equilibrium problem and provide a number of valid inequalities to improve the quality of the relaxation. If a rank-1 solution to this SDP is found, then an exact Nash equilibrium can be recovered. We show that, for a strictly competitive game, our SDP is guaranteed to return a rank-1 solution. We propose two algorithms based on the iterative linearization of smooth nonconvex objective functions whose global minima by design coincide with rank-1 solutions. Empirically, we demonstrate that these algorithms often recover solutions of rank at most 2 and ɛ close to zero. Furthermore, we prove that if a rank-2 solution to our SDP is found, then a 5 11 -Nash equilibrium can be recovered for any game, or a 1 3 -Nash equilibrium for a symmetric game. We then show how our SDP approach can address two (NP-hard) problems of economic interest: finding the maximum welfare achievable under any Nash equilibrium, and testing whether there exists a Nash equilibrium where a particular set of strategies is not played. Finally, we show the connection between our SDP and the first level of the Lasserre/sum of squares hierarchy.

Keywords: Nash equilibria; semidefinite programming; correlated equilibria (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0960 (application/pdf)

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:inm:orijoc:v:33:y:2021:i:2:p:607-628

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().