论文标题
2播放器NASH平衡的平滑复杂性
Smoothed Complexity of 2-player Nash Equilibria
论文作者
论文摘要
我们证明，即使在平滑的分析设置中，计算带有$ [ - 1,1] $收益的两人（$ n \ times n $）游戏的NASH平衡是PPAD-HARD（在随机减少的情况下），即使在平滑的分析设置中，具有恒定幅度的噪音。这给了Spielman和Teng [ST06]和Cheng，Deng和Teng [CDT09]的猜想有很大的负面答案。 与先前的工作相反，证明了通过幅度$ 1/\ operatatorname {poly}（n）$ [CDT09]平滑后的ppad-hards，我们的平滑复杂性结果未通过nash equilibria的近似值而证明。这是必需的，因为NASH平衡可以近似于准多项式时间的恒定误差[LMM03]。因此，我们的结果在两人游戏中分离了纳什均衡的平滑复杂性和近似的近似值。 我们减少的关键要素是使用随机的零和游戏用作小工具来生产两人游戏，即使在平滑后也保持困难。我们的分析至关重要地表明，随机零和游戏的所有NASH平衡远非纯净（具有很高的概率），即使平滑后，这仍然是正确的。
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 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/\operatorname{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.
