Introduction
In the field of algorithmic game theory, the Nash Equilibrium (NE) serves as a fundamental solution concept. However, it is well-known that NE can sometimes include "unreasonable" strategy profiles, such as those involving non-credible threats or weakly dominated actions. To address these shortcomings, economists developed refinements like Selten’s Trembling-Hand Perfect Equilibrium and Myerson’s Proper Equilibrium. These concepts introduce robustness by assuming players might make infinitesimal errors (or "trembles"), forcing them to choose strategies that remain optimal even in the face of slight irrationality.
While the complexity of these refinements is established for general games (often PPAD- or FIXP-complete), their status within potential games remained an open question. Potential games are a significant class where players' incentives are aligned with a single global potential function, ensuring the existence of pure-strategy equilibria and typically placing them in the complexity class PLS (Polynomial Local Search). This paper settles the computational complexity of these refinements in potential games.
Methodological Innovations
The authors introduce several novel techniques to tackle the symbolic nature of equilibrium refinements:
- Symbolic Best-Response Dynamics: Rather than using a fixed small value for trembles ($\epsilon$), the authors treat $\epsilon$ as a symbolic variable. By employing polynomial interpolation, they evaluate utilities as polynomials, enabling lexicographical strategy comparisons.
- Multilinear Arithmetic Circuits: To handle concise games with many players, the authors use circuits to represent utility functions, avoiding computational bottlenecks like "repeated squaring" and ensuring efficient evaluation.
- Fractional Interpolation: This technique allows the transformation of strongly polynomial-time algorithms into "perturbed" versions capable of finding refined equilibria symbolically.
Key Theoretical Insights
The research reveals a nuanced landscape of complexity for equilibrium refinements:
Complexity Parity and the Verification Paradox
For pure strategies, the paper demonstrates that computing a perfect or proper equilibrium is PLS-complete, matching the complexity of finding a standard Nash equilibrium. This suggests that refinements do not inherently increase the search complexity in this setting. However, a "Verification Paradox" emerges: while finding an equilibrium is in PLS, verifying whether a given strategy profile is a perfect equilibrium is NP-hard. This stands in stark contrast to standard Nash equilibria, which are efficiently verifiable.
Dynamics and Precision
The study also explores the convergence of best-response dynamics. The authors find exponential separations: the path to a refined equilibrium can be exponentially longer than the path to a standard NE. Furthermore, in 3-player potential games, the required precision for the "tremble" ($\epsilon$) may need to be doubly exponentially small to ensure geometric proximity to the true perfect equilibrium, refining previous bounds in the literature.
Summary of Complexity Results
The following table summarizes the main complexity results established in this work across different game classes and equilibrium types.
Tractable Subclasses and Efficiency
Beyond hardness results, the paper identifies tractable cases. For symmetric matroid and network congestion games, perfect equilibria can be found in polynomial time (P). In polymatrix potential games, computing refinements is shown to be in CLS (Continuous Local Search), suggesting they are amenable to gradient-descent-style algorithms. Additionally, the authors prove that refined equilibria can significantly improve the Price of Anarchy, offering higher social welfare than the worst-case Nash equilibrium in polynomial degree-$d$ congestion games.
Conclusion and Future Work
This work provides a comprehensive map of the complexity of equilibrium refinements in potential games. Future research directions include determining the exact complexity of mixed Nash equilibria in general potential games (currently between PLS and FIXP) and investigating the complexity of asymmetric matroid congestion games. The symbolic optimization techniques developed here also hold promise for broader applications in constrained optimization and avoiding suboptimal local optima in gradient descent landscapes.
Summary updated