Semidefinite programming and nash equilibria in bimatrix games

Amir Ali Ahmadi, Jeffrey Zhang

Research output: Contribution to journalArticlepeer-review

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 115 -Nash equilibrium can be recovered for any game, or a 13-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.

Original languageEnglish (US)
Pages (from-to)607-628
Number of pages22
JournalINFORMS Journal on Computing
Volume33
Issue number2
DOIs
StatePublished - Mar 2021

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Correlated equilibria
  • Nash equilibria
  • Semidefinite programming

Fingerprint

Dive into the research topics of 'Semidefinite programming and nash equilibria in bimatrix games'. Together they form a unique fingerprint.

Cite this