The Complexity of Sparse Win-Lose Bimatrix Games

Abstract

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

44 pages; EC 2026