The Complexity of Sparse Win-Lose Bimatrix Games
2026-02-20 • Computational Complexity
Computational ComplexityComputer Science and Game Theory
AI summaryⓘ
The authors show that finding an approximate Nash equilibrium in certain simple games called win-lose bimatrix games is computationally hard. Specifically, the difficulty holds even when each player has only three options with limited connections (3-sparse). This result is precise because when there are only two options per player with limited connections (2-sparse), the problem is easier and can be solved quickly. Essentially, they pinpoint the boundary between easy and hard versions of this problem.
Nash equilibriumwin-lose bimatrix gamesparsityPPAD-hardapproximate equilibriuminverse-polynomial epsiloncomputational complexity3-sparse games2-sparse games
Authors
Eleni Batziou, John Fearnley, Abheek Ghosh, Rahul Savani
Abstract
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.