The Complexity of Sparse Win-Lose Bimatrix Games

Eleni Batziou, John Fearnley, Abheek Ghosh +1

We prove that computing an $\epsilon$-approximate Nash equilibrium of a win-lose bimatrix game with constant sparsity is PPAD-hard for inverse-polynomial $\epsilon$. Our result holds for 3-spars…