Smoothed Complexity of 2-player Nash Equilibria

Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins +1

We prove that computing a Nash equilibrium of a two-player ($n\times n$) game with payoffs in $[-1,1]$ is PPAD-hard (under randomized reductions) even in the smoothed analysis set…