TY - JOUR
T1 - Nash equilibria in perturbation-stable games
AU - Balcan, Maria Florina
AU - Braverman, Mark
N1 - Funding Information:
†This work was done in part while the author was a member of Microsoft Research NE. Research supported in part by NSF Awards, DMS-1128155, CCF-1525342, and CCF-1149888, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry.
Funding Information:
∗Supported in part by NSF grants CCF-0953192 and CCF-1101283, ONR grant N00014-09-1-0751, AFOSR grant FA9550-09-1-0538, a Google Research Award, and a Microsoft Faculty Fellowship. This work was done in part while the author was visiting Microsoft Research NE.
Funding Information:
Supported in part by NSF grants CCF-0953192 and CCF-1101283, ONR grant N00014-09-1-0751, AFOSR grant FA9550- 09-1-0538, a Google Research Award, and a Microsoft Faculty Fellowship. This work was done in part while the author was visiting Microsoft Research NE. This work was done in part while the author was a member of Microsoft Research NE. Research supported in part by NSF Awards, DMS-1128155, CCF-1525342, and CCF-1149888, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry.
Publisher Copyright:
© 2017 Maria-Florina Balcan and Mark Braverman.
PY - 2017/11/13
Y1 - 2017/11/13
N2 - Motivated by the fact that in many game-theoretic settings, the game analyzed is only an approximation to the game being played, in this work we analyze equilibrium computation for the broad and natural class of bimatrix games that are stable under perturbations. We specifically focus on games with the property that small changes in the payoff matrices do not cause the Nash equilibria of the game to fluctuate wildly. For such games we show how one can compute approximate Nash equilibria more efficiently than the general result of Lipton et al. (EC’03), by an amount that depends on the degree of stability of the game and that reduces to their bound in the worst case. Additionally, we show that for stable games, the approximate equilibria found will be close in variation distance to true equilibria, and moreover this holds even if we are given as input only a perturbation of the actual underlying stable game. For uniformly stable games, where the equilibria fluctuate at most quasi-linearly in the extent of the perturbation, we get a particularly dramatic improvement. Here, we achieve a fully quasi-polynomial-time approximation scheme, that is, we can find 1=poly(n)- approximate equilibria in quasi-polynomial time. This is in marked contrast to the general class of bimatrix games for which finding such approximate equilibria is PPAD-hard. In particular, under the (widely believed) assumption that PPAD is not contained in quasipolynomial time, our results imply that such uniformly stable games are inherently easier for computation of approximate equilibria than general bimatrix games.
AB - Motivated by the fact that in many game-theoretic settings, the game analyzed is only an approximation to the game being played, in this work we analyze equilibrium computation for the broad and natural class of bimatrix games that are stable under perturbations. We specifically focus on games with the property that small changes in the payoff matrices do not cause the Nash equilibria of the game to fluctuate wildly. For such games we show how one can compute approximate Nash equilibria more efficiently than the general result of Lipton et al. (EC’03), by an amount that depends on the degree of stability of the game and that reduces to their bound in the worst case. Additionally, we show that for stable games, the approximate equilibria found will be close in variation distance to true equilibria, and moreover this holds even if we are given as input only a perturbation of the actual underlying stable game. For uniformly stable games, where the equilibria fluctuate at most quasi-linearly in the extent of the perturbation, we get a particularly dramatic improvement. Here, we achieve a fully quasi-polynomial-time approximation scheme, that is, we can find 1=poly(n)- approximate equilibria in quasi-polynomial time. This is in marked contrast to the general class of bimatrix games for which finding such approximate equilibria is PPAD-hard. In particular, under the (widely believed) assumption that PPAD is not contained in quasipolynomial time, our results imply that such uniformly stable games are inherently easier for computation of approximate equilibria than general bimatrix games.
KW - Algorithmic game theory
KW - Approximation algorithms
KW - Beyond worst-case analysis
KW - Nash equilibrium
KW - Perturbation stability
UR - http://www.scopus.com/inward/record.url?scp=85044718215&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85044718215&partnerID=8YFLogxK
U2 - 10.4086/toc.2017.v013a013
DO - 10.4086/toc.2017.v013a013
M3 - Article
AN - SCOPUS:85044718215
SN - 1557-2862
VL - 13
SP - 1
EP - 31
JO - Theory of Computing
JF - Theory of Computing
ER -