Constant rank bimatrix games are PPAD-hard
Constant rank bimatrix games are PPAD-hard
复制标题
常秩双矩阵游戏是 PPAD 困难的
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
R. Mehta
中科院分区：
文献类型：
--
作者：
R. Mehta
双矩阵对策（A，B）的秩定义为秩（A + B）。计算秩为0的纳什均衡（NE），即，零和博弈等价于线性规划（von Neumann'28，Dantzig'51）。2005年，Kannan和Theobald给出了常秩博弈的FPTAS，并提出了是否存在一个多项式时间算法来计算精确的NE。Adsul et. al.（2011）对1级游戏肯定地回答了这个问题，留下2级及以上的未解决问题。本文证明了秩≥ 3的对策的NE计算是PPAD困难的，解决了一个十年之久的公开问题。有趣的是，这是FPTAS的问题第一次被证明是PPAD困难的。我们的减少绕过图形游戏和游戏小工具，并提供了一个更简单的证明PPAD硬度NE计算双矩阵游戏。此外，我们得到：·2D-Linear-FIXP和PPAD之间的等价性，改进了Etessami和Yannakakis（2007）关于Linear-FIXP和PPAD之间等价性的结果。·具有纳什均衡凸集的双矩阵博弈中的NE计算与求解简单的随机博弈一样困难[12]。·计算秩≥ 6的对称双矩阵博弈的对称NE是PPAD困难的。·计算（Linear-FIXP）分段线性函数的1/poly（n）近似不动点是PPAD困难的。2级游戏的地位仍然没有得到解决。
The rank of a bimatrix game (A, B) is defined as rank(A + B). Computing a Nash equilibrium (NE) of a rank-0, i.e., zero-sum game is equivalent to linear programming (von Neumann'28, Dantzig'51). In 2005, Kannan and Theobald gave an FPTAS for constant rank games, and asked if there exists a polynomial time algorithm to compute an exact NE. Adsul et. al. (2011) answered this question affirmatively for rank-1 games, leaving rank-2 and beyond unresolved. In this paper we show that NE computation in games with rank ≥ 3, is PPAD-hard, settling a decade long open problem. Interestingly, this is the first instance that a problem with an FPTAS turns out to be PPAD-hard. Our reduction bypasses graphical games and game gadgets, and provides a simpler proof of PPAD-hardness for NE computation in bimatrix games. In addition, we get: • An equivalence between 2D-Linear-FIXP and PPAD, improving a result by Etessami and Yannakakis (2007) on equivalence between Linear-FIXP and PPAD. • NE computation in a bimatrix game with convex set of Nash equilibria is as hard as solving a simple stochastic game [12]. • Computing a symmetric NE of a symmetric bimatrix game with rank ≥ 6 is PPAD-hard. • Computing a 1/poly(n)-approximate fixed-point of a (Linear-FIXP) piecewise-linear function is PPAD-hard. The status of rank-2 games remains unresolved.