Name
Abstract | ||
|---|---|---|
We prove that computing a Nash equilibrium of a two-player ( n×n) game with payoffs in [-1, 1] is PPAD-hard (under randomized reductions) even in the smoothed analysis setting, smoothing with noise of constant magnitude. This gives a strong negative answer to conjectures of Spielman and Teng [ST06] and Cheng, Deng, and Teng [CDT09]. In contrast to prior work proving PPAD-hardness after smoothing by noise of magnitude 1/poly(n) [CDT09], our smoothed complexity result is not proved via hardness of approximation for Nash equilibria. This is by necessity, since Nash equilibria can be approximated to constant error in quasi-polynomial time [LMM03]. Our results therefore separate smoothed complexity and hardness of approximation for Nash equilibria in two-player games. The key ingredient in our reduction is the use of a random zero-sum game as a gadget to produce two-player games which remain hard even after smoothing. Our analysis crucially shows that all Nash equilibria of random zero-sum games are far from pure (with high probability), and that this remains true even after smoothing. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1109/FOCS46700.2020.00034 | 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Nash equilibrium,PPAD,zero-sum game,smoothed analysis,smoothed complexity,anticoncentration | Conference | 1523-8288 |
ISBN | Citations | PageRank |
978-1-7281-9622-0 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shant Boodaghians | 1 | 0 | 2.03 |
| Joshua Brakensiek | 2 | 2 | 6.80 |
| Samuel Hopkins | 3 | 88 | 9.47 |
| Aviad Rubinstein | 4 | 179 | 24.66 |