Ruta Mehta: (Essentially) Resolving the Complexity of Constant Rank Bimatrix Games

The rank of a bimatrix game (A, B) is defined as the rank of (A+B). For zero-sum games, i.e., rank-0, von Neumann (1928) showed that Nash equilibrium are min-max strategies, which is equivalent to the linear programming duality. We solve the open question of Kannan and Theobald (2005) of designing an efficient algorithm for rank-1 games. The main difficulty is that the set of equilibria can be disconnected. We circumvent this by moving to a space of rank-1 games which contains our game (A, B), and defining a quadratic program whose optimal solutions are Nash equilibria of all games in this space. We then isolate the Nash equilibrium of (A, B) as the fixed point of a single variable function which can be found in polynomial time via an easy binary search.

The next immediate question to consider is rank-2 games, or in general constant rank games, for which an FPTAS is already known due to Kannan and Theobald (2005). We show that constant rank games are PPAD-hard in general by reducing 2D-Brouwer to rank-3 bimatrix games. This is the first time that a problem with an FPTAS turns out to be PPAD-hard. Our reduction gives a simpler proof of PPAD-hardness for bimatrix games. This leaves the status of only rank-2 games unresolved.

The first part of the talk is based on a joint work with Bharat Adsul, Jugal Garg and Milind Sohoni.