TY - GEN

T1 - Constant rank bimatrix games are PPAD-hard

AU - Mehta, Ruta

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - 2D-Brouwer

KW - Constant rank

KW - LCP

KW - Linear-FIXP

KW - PPAD-hard

UR - http://www.scopus.com/inward/record.url?scp=84904316928&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904316928&partnerID=8YFLogxK

U2 - 10.1145/2591796.2591835

DO - 10.1145/2591796.2591835

M3 - Conference contribution

AN - SCOPUS:84904316928

SN - 9781450327107

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 545

EP - 554

BT - STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 2014

Y2 - 31 May 2014 through 3 June 2014

ER -