Search Mailing List Archives
[theory-seminar] Theory Lunch 12/03: Joshua Brakensiek
wajc at stanford.edu
Wed Dec 2 09:00:01 PST 2020
Theory lunch will be happening tomorrow at noon (PDT), at our gather space:
Josh will tell us about *S**moothed Complexity of 2-player Nash Equilibria.*
We prove that computing a Nash equilibrium of a two-player (n x 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
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.
Joint work with Shant Boodaghians, Samuel B. Hopkins, and Aviad Rubinstein.
*Pro tip:* To join the zoom talk:
(1) go to the lecture hall,
(2) grab a seat, and
(3)* press X to join the zoom lecture*.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar