How hard is it to approximate the best Nash equilibrium?
How hard is it to approximate the best Nash equilibrium?
复制标题
DOI：
10.1137/090766991
复制
发表时间：
2009-01
期刊：
影响因子：
--
通讯作者：
Elad Hazan;Robert Krauthgamer
中科院分区：
文献类型：
--
作者：
Elad Hazan;Robert Krauthgamer
在两人游戏中，寻求对NASH平衡的PTA，旨在通过找到近似平衡来规避（确切的）NASH平衡的PPAD完整性，并已成为算法游戏理论的主要开放问题问题是找到最大化某个目标的同等问题，例如社交福利。但是，经济行为1989年。 ]。我们结果的一种解释是，对NASH等效的PTA的追求不应扩展到PTA，以找到最佳的NASH等价brium，这与迄今为止使用的某些算法技术相反（例如，采样和枚举）是从现代组合中的一个臭名昭著的问题中减少的，是在随机图中找到一个种植（但隐藏的）集团（n，1/2）。种植的大小k = O（log n）。对于更大的集团大小k =ω（√n）有效。
The quest for a PTAS for Nash equilibrium in a two-player game seeks to circumvent the PPAD-completeness of an (exact) Nash equilibrium by finding an approximate equilibrium, and has emerged as a major open question in Algorithmic Game Theory. A closely related problem is that of finding an equilibrium maximizing a certain objective, such as the social welfare. This optimization problem was shown to be NP-hard by Gilboa and Zemel [Games and Economic Behavior 1989]. However, this NP-hardness is unlikely to extend to finding an approximate equilibrium, since the latter admits a quasi-polynomial time algorithm, as proved by Lipton, Markakis and Mehta [Proc. of 4th EC, 2003]. We show that this optimization problem, namely, finding in a two-player game an approximate equilibrium achieving large social welfare is unlikely to have a polynomial time algorithm. One interpretation of our results is that the quest for a PTAS for Nash equilibrium should not extend to a PTAS for finding the best Nash equilibrium, which stands in contrast to certain algorithmic techniques used so far (e.g. sampling and enumeration). Technically, our result is a reduction from a notoriously difficult problem in modern Combinatorics, of finding a planted (but hidden) clique in a random graph G(n, 1/2). Our reduction starts from an instance with planted clique size k = O(log n). For comparison, the currently known algorithms due to Alon, Krivelevich and Sudakov [Random Struct. & Algorithms, 1998], and Krauthgamer and Feige [Random Struct. & Algorithms, 2000], are effective for a much larger clique size k = Ω(√n).