Avoiding the Worst: The Computational Complexity of Not Worst-Responding

Mete \c{S}eref Ahunbay, Paul W. Goldberg, Edwin Lock, Panayotis Mertikopoulos, Bary S. R. Pradelski and Bassel Tarbush

Papers from arXiv.org

Abstract: Finding, counting, or determining the existence of pure Nash equilibria, where players must play optimally given the others' actions, are known to be computationally intractable problems. We ask whether weakening optimality to the requirement that each player merely avoid worst responses yields tractable solution concepts. We show that it does not: any solution concept with this minimal guarantee is broadly "as intractable" as pure Nash equilibrium. In general games, determining the existence of no-worst response action profiles is NP-complete, and counting them is #P-complete. In potential games, where existence is guaranteed, the search problem is PLS-complete. However, a class of graphical games reveal a wedge in terms of complexity. Computational intractability therefore stems not only from the requirement of optimality, but from the interactivity of games that makes even a minimal rationality guarantee for each player intractable. 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.

Date: 2026-02, Revised 2026-09
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://arxiv.org/pdf/2602.10966 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2602.10966

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().