TY - JOUR
T1 - Semidefinite programming and nash equilibria in bimatrix games
AU - Ahmadi, Amir Ali
AU - Zhang, Jeffrey
N1 - Funding Information: Funding: This work was supported by the Alfred P. Sloan Foundation, a SEAS Innovation Award, an Air Force Office of Scientific Research (AFOSR) Young Investigator Award, an AFOSR MURI Award, a Defense Advanced Research Projects Agency Young Faculty Award, a Google Faculty Award, and a National Science Foundation CAREER Award. Publisher Copyright: Copyright: © 2020 INFORMS
PY - 2021/3
Y1 - 2021/3
N2 - 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.
AB - 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.
KW - Correlated equilibria
KW - Nash equilibria
KW - Semidefinite programming
UR - http://www.scopus.com/inward/record.url?scp=85114680340&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85114680340&partnerID=8YFLogxK
U2 - https://doi.org/10.1287/ijoc.2020.0960
DO - https://doi.org/10.1287/ijoc.2020.0960
M3 - Article
SN - 0899-1499
VL - 33
SP - 607
EP - 628
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
IS - 2
ER -