The Complexity of Sparse Win-Lose Bimatrix Games

Authors: Eleni Batziou, John Fearnley, Abheek Ghosh, Rahul Savani

We prove that computing an $ε$-approximate Nash equilibrium of a win-lose bimatrix game with constant sparsity is PPAD-hard for inverse-polynomial $ε$. Our result holds for 3-sparse games, which is tight given that 2-sparse win-lose bimatrix games can be solved in polynomial time.