Two-Player Constant Rank Games are PPAD-Hard

Finding Nash equilibrium in a two-player normal form game (2-Nash) is an extensively studied problem 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 (DGP'06, CDT'06), while in 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 defined 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. (2011) answered this question affirmatively for rank-1 games, leaving rank-2 and beyond unresolved.

In this talk I will 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, central to the previous approaches, and instead exploits relations between LPs, linear complementarity problems (LCPs) and bimatrix games. In the process we derive a simpler proof of PPAD-hardness for NE computation in bimatrix games. In addition we get a number of results that I will describe in the talk.

Rank-2 case has been resolved recently by Chen et al.