TY - JOUR

T1 - Constant rank two-player games are PPAD-hard

AU - Mehta, Ruta

N1 - Funding Information:
∗Received by the editors July 24, 2015; accepted for publication (in revised form) July 10, 2017; published electronically October 30, 2018. A preliminary version of this paper appeared in the Proceedings of the 46th ACM Symposium on Theory of Computing (STOC’14). http://www.siam.org/journals/sicomp/47-5/M103233.html Funding: This research was supported by NSF grant CCF-1216019. †Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801 (mehta.ruta@gmail.com). The work was done when the author was a postdoctoral fellow at Georgia Institute of Technology.
Funding Information:
This research was supported by NSF grant CCF-1216019.
Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics

PY - 2018

Y1 - 2018

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

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

KW - Bimatrix games

KW - Constant rank

KW - LCP

KW - Nash equilibrium

KW - PPAD-hard

KW - Parameterized LP

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

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

U2 - 10.1137/15M1032338

DO - 10.1137/15M1032338

M3 - Article

AN - SCOPUS:85056125783

SN - 0097-5397

VL - 47

SP - 1858

EP - 1887

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 5

ER -