Optimization Online


Semidefinite Programming and Nash Equilibria in Bimatrix Games

Amir Ali Ahmadi (a_a_a***at***princeton.edu)
Jeffrey Zhang (jeffz***at***princeton.edu)

Abstract: We explore the power of semidefinite programming (SDP) for finding additive epsilon-approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic programming formulation of the Nash equilibrium (NE) 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 NE can be recovered. We show that for a strictly competitive game, our SDP is guaranteed to return a rank-1 solution. Furthermore, we prove that if a rank-2 solution to our SDP is found, then a 5/11-NE can be recovered for any game, or a 1/3-NE for a symmetric game. We propose two algorithms based on iterative linearization of smooth nonconvex objective functions that are designed so that their global minima coincide with rank-1 solutions. Empirically, we demonstrate that these algorithms often recover solutions of rank at most two and epsilon close to zero. We then show how our SDP approach can address two (NP-hard) problems of economic interest: finding the maximum welfare achievable under any NE, and testing whether there exists a NE 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: Semidefinite optimization, Game theory, Approximate Nash equilibria

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Other Topics (Game Theory )

Citation: Submitted for publication

Download: [PDF]

Entry Submitted: 06/26/2017
Entry Accepted: 06/26/2017
Entry Last Modified: 08/14/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society