Constant rank two-player games are PPAD-hard

Finding a Nash equilibrium in a two-player normal form game (2-Nash) is one of the most extensively studied problems within mathematical economics as well as theoretical computer science. Such a game can be represented by two payoff matrices A and B, one for each player. 2-Nash is PPAD-complete in general, while in the case of zero-sum games (B = −A) the problem reduces to LP and hence is in P. Extending the notion of zero-sum, in 2005, Kannan and Theobald [Econom. Theory, 42 (2010), pp. 157-174] defined the rank of game (A, B) as rank(A + B), e.g., rank-0 are zero-sum games. They gave an FPTAS for constant rank games and asked if there exists a polynomial time algorithm to compute an exact Nash equilibrium (NE). Adsul et al. [Proceedings of the ACM Symposium on the Theory of Computing, 2011, pp. 195-204] 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 two-player games. In addition, we show the following: (i) an equivalence between two-dimensional Linear-FIXP and PPAD, improving on a result of Etessami and Yannakakis [SIAM J. Comput., 39 (2010), pp. 2531-2597] on equivalence between Linear-FIXP and PPAD; (ii) NE computation in a two-player game with convex set of Nash equilibria is as hard as solving a simple stochastic game [A. Condon, Inform. and Comput., 96 (1992), pp. 203-224]; (iii) computing a symmetric NE of a symmetric two-player game with rank ≥ 6 is PPAD-hard; (iv) computing a 1/poly(n)-approximate fixed-point of a piecewise-linear function is PPAD-hard .