Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 12/03: Joshua Brakensiek

David Wajc wajc at stanford.edu
Wed Dec 2 09:00:01 PST 2020


Hi all,

Theory lunch will be happening tomorrow at noon (PDT), at our gather space:
https://gather.town/app/lR6jRBPK44nZ7V68/StanfordTheory (*password:*
 SongComplexity).
Josh will tell us about *S**moothed Complexity of 2-player Nash Equilibria.*

*Abstract:*
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
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.

Joint work with Shant Boodaghians, Samuel B. Hopkins, and Aviad Rubinstein.

Cheers,
David

PS
*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...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20201202/a01eda4b/attachment-0001.html>


More information about the theory-seminar mailing list