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

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 trac