Sparse Games Are Hard

A two-player game is sparse if most of its payoff entries are zeros. We show that the problem of computing a Nash equilibrium remains PPAD-hard to approximate in fully polynomial time for sparse games. On the algorithmic side, we give a simple and polynomial-time algorithm for finding exact Nash equilibria in a class of sparse win-lose games