The Computational Intractability of Not Worst Responding
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917268170997760 |
|---|---|
| author | Ahunbay, Mete Şeref Goldberg, Paul W. Lock, Edwin Mertikopoulos, Panayotis Pradelski, Bary S. R. Tarbush, Bassel |
| author_facet | Ahunbay, Mete Şeref Goldberg, Paul W. Lock, Edwin Mertikopoulos, Panayotis Pradelski, Bary S. R. Tarbush, Bassel |
| contents | Finding, counting, or determining the existence of Nash equilibria, where players must play optimally given each others' actions, are known to be computational intractable problems. We ask whether weakening optimality to the requirement that each player merely avoid worst responses -- arguably the weakest meaningful rationality criterion -- yields tractable solution concepts. We show that it does not: any solution concept with this minimal guarantee is ``as intractable'' as pure Nash equilibrium. In general games, determining the existence of no-worst-response action profiles is NP-complete, finding one is NP-hard, and counting them is #P-complete. In potential games, where existence is guaranteed, the search problem is PLS-complete. Computational intractability therefore stems not only from the requirement of optimality, but also from the requirement of a minimal rationality guarantee for each player. Moreover, relaxing the latter requirement gives rise to a tractability trade-off between the strength of individual rationality guarantees and the fraction of players satisfying them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10966 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Computational Intractability of Not Worst Responding Ahunbay, Mete Şeref Goldberg, Paul W. Lock, Edwin Mertikopoulos, Panayotis Pradelski, Bary S. R. Tarbush, Bassel Computer Science and Game Theory Theoretical Economics Finding, counting, or determining the existence of Nash equilibria, where players must play optimally given each others' actions, are known to be computational intractable problems. We ask whether weakening optimality to the requirement that each player merely avoid worst responses -- arguably the weakest meaningful rationality criterion -- yields tractable solution concepts. We show that it does not: any solution concept with this minimal guarantee is ``as intractable'' as pure Nash equilibrium. In general games, determining the existence of no-worst-response action profiles is NP-complete, finding one is NP-hard, and counting them is #P-complete. In potential games, where existence is guaranteed, the search problem is PLS-complete. Computational intractability therefore stems not only from the requirement of optimality, but also from the requirement of a minimal rationality guarantee for each player. Moreover, relaxing the latter requirement gives rise to a tractability trade-off between the strength of individual rationality guarantees and the fraction of players satisfying them. |
| title | The Computational Intractability of Not Worst Responding |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2602.10966 |