Skip to main content

Nash Equilibria in Perturbation-Stable Games

Author(s): Balcan, Maria-Florina; Braverman, Mark

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1d25p
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBalcan, Maria-Florina-
dc.contributor.authorBraverman, Mark-
dc.date.accessioned2021-10-08T19:44:53Z-
dc.date.available2021-10-08T19:44:53Z-
dc.date.issued2017en_US
dc.identifier.citationBalcan, Maria-Florina, and Mark Braverman. "Nash equilibria in perturbation-stable games." Theory of Computing 13, no. 13 (2017): pp. 1-31. doi:10.4086/toc.2017.v013a013en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1d25p-
dc.description.abstractMotivated 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 quasi-polynomial time, our results imply that such uniformly stable games are inherently easier for computation of approximate equilibria than general bimatrix games.en_US
dc.format.extent1 - 31en_US
dc.language.isoen_USen_US
dc.relation.ispartofTheory of Computingen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleNash Equilibria in Perturbation-Stable Gamesen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.4086/toc.2017.v013a013-
dc.identifier.eissn1557-2862-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
NashEquilibriaPerturbationStableGames.pdf325.06 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.