Abstract
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.
Introduction
In game theory, the Nash Equilibrium represents a state of mutual optimality: no player can improve their payoff by unilaterally changing their strategy. However, finding such equilibria in "succinct" games—those with many players or actions described by rules rather than exhaustive tables—is notoriously difficult, often classified as NP-hard or PLS-complete.
A natural question arises: does "bounded rationality" simplify these problems? If we relax the requirement for perfect optimization, can we find stable outcomes more efficiently? This research investigates the most extreme relaxation of rationality: the no-worst-response criterion. In this model, players are only required to avoid their absolute worst possible move. If even this minimal rationality guarantee fails to provide tractability, it suggests that computational hardness is a fundamental property of multi-agent systems, independent of the precision of optimization.
Methodology
The authors establish their results by analyzing Circuit Games. In these games, players' payoffs are not given by a table but are computed by Boolean circuits. This representation allows for the efficient description of games with a large number of players and actions.
The study employs several key complexity-theoretic techniques:
- Reductions from CircuitSAT: To demonstrate hardness in general games, the authors show that finding a "no-worst-response" profile is equivalent to solving the NP-complete problem of circuit satisfiability.
- Potential Games and PLS-Completeness: In potential games, where a global function tracks individual incentives, an equilibrium always exists. However, the authors prove that finding even a weak equilibrium remains PLS-complete through reductions from local optimization problems.
- The Probabilistic Method: Constructing the necessary "circuit gadgets" for potential games required the Lovász Local Lemma, a sophisticated combinatorial tool used to prove the existence of structures with specific properties.
- Threshold Analysis: The research also explores the boundary of tractability by varying the fraction of players required to act rationally.
Key Insights
The core finding is that computational difficulty arises not from the depth of optimization (finding the best move) but from the universality of the requirement (every player meeting a minimum bar). When 100% of players must avoid their worst response, the resulting constraints interlock to create a problem space as complex as that of a pure Nash Equilibrium.
Furthermore, the authors identified a "knife-edge" property regarding tractability. The problem is highly sensitive to the strictness of the rationality requirement. If the requirement is slightly relaxed—either by allowing a small fraction of players to act irrationally or by lowering the definition of a "good" move—the problem can transition from NP-hard to solvable in randomized polynomial time (RP). This suggests that the plausibility of economic models is deeply linked to their underlying computational complexity.
Results and Complexity Bounds
The paper provides rigorous complexity classifications for the no-worst-response concept across different game classes:
- General Games: Determining the existence of a no-worst-response profile is NP-complete. Finding such a profile is NP-hard, and counting them is #P-complete.
- Potential Games: While existence is guaranteed, the search problem is PLS-complete, implying that simple improvement dynamics may take exponential time to converge.
- The Tractability Threshold: The authors define a sharp boundary for finding a profile where a fraction $\alpha$ of players choose an action within their top-$\beta$ fraction of payoffs:
- Tractable (in RP) if $\alpha < \beta$.
- Intractable (NP-hard) if $\alpha > \beta$.
Intuitively, if one only needs "fairly good" responses from a "fairly small" group, random sampling is effective. However, requiring "better than average" responses from a "larger than average" group triggers computational intractability.
Discussion and Future Directions
This work highlights that even minimal rationality does not bypass the inherent complexity of multi-agent coordination. However, several avenues for future research remain:
- Average-Case Complexity: While the paper proves worst-case hardness, real-world games might possess structures that make them easier to solve on average.
- Mixed Strategies: The current analysis is restricted to pure strategies. Exploring the complexity of no-worst-response in the context of mixed strategies (probability distributions) remains an open question.
- Learning Dynamics: Future work could investigate whether simple learning algorithms converge to these weak equilibria more rapidly than they do to standard Nash Equilibria in practical scenarios.
- Refining the Threshold: There remains a small mathematical gap in the threshold theorem (Theorem 3) that could be further tightened.
Summary updated