The Complexity of Sparse Win-Lose Bimatrix Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917284374642688 |
|---|---|
| author | Batziou, Eleni Fearnley, John Ghosh, Abheek Savani, Rahul |
| author_facet | Batziou, Eleni Fearnley, John Ghosh, Abheek Savani, Rahul |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18380 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Complexity of Sparse Win-Lose Bimatrix Games Batziou, Eleni Fearnley, John Ghosh, Abheek Savani, Rahul Computational Complexity Computer Science and Game Theory Theoretical Economics 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. |
| title | The Complexity of Sparse Win-Lose Bimatrix Games |
| topic | Computational Complexity Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2602.18380 |