Abstract
Verifying whether a multiplayer game is concave or monotone is essential for guaranteeing the existence of Nash equilibria and the convergence of decentralized learning algorithms. For polynomial games, where utilities are multivariate polynomials, we prove that these verification tasks are NP-hard. To address this, we propose a hierarchy of semidefinite programs (SDPs) based on Sum-of-Squares (SOS) optimization. This framework provides a computationally efficient way to certify these properties and allows for the approximation of arbitrary games by their "closest" well-behaved counterparts.
Introduction
In the study of strategic interactions, "concave games" represent a gold standard for tractability. When players' payoffs are concave in their own actions, a Nash equilibrium is guaranteed to exist. If a game further satisfies "monotonicity," the equilibrium is often unique, and simple algorithms are guaranteed to find it.
Despite their importance, verifying these properties in "polynomial games"—where utilities are complex multivariate polynomials and strategy sets are defined by polynomial constraints—has remained an open challenge. Verifying concavity or monotonicity in this context requires checking if a Hessian or Jacobian matrix is negative semidefinite over a continuous region, a problem that is inherently "infinite" in nature.
Complexity and Classification
The authors first establish that certifying concavity or monotonicity is strongly NP-hard, even for relatively simple cases such as cubic polynomials over boxes or quartic polynomials over simplices. This result explains the historical reliance on highly structured, linear game classes.
To navigate this complexity, it is helpful to understand the relationships between different game classes.
As shown in the figure above, monotone games form a subset of concave games, with strictly monotone games residing at the core. The paper focuses on bridging the gap between these theoretical definitions and practical certification.
Methods: Sum-of-Squares Hierarchies
To overcome NP-hardness, the paper leverages Sum-of-Squares (SOS) optimization. The core approach involves:
- SDP Relaxations: The condition for monotonicity is rephrased using the Rayleigh-Ritz theorem, focusing on the maximum eigenvalue of the symmetrized Jacobian. This allows for the construction of a hierarchy of increasingly tight semidefinite programming (SDP) relaxations.
- Certification Guarantee: A key theoretical result is the "Almost All" guarantee: measure-theoretically, almost all monotone or concave games are strictly so. This ensures that they can be certified at some finite level of the SOS hierarchy.
- SOS-Monotone Approximation: The authors introduce "SOS-monotone" games, a new class that is dense within the space of all monotone games. They provide an algorithm to compute the "closest" SOS-monotone game to any given polynomial game by solving a single SDP, effectively regularizing ill-behaved games.
Experimental Evaluation
The framework was evaluated on both canonical examples and synthetic polynomial games:
- Extensive-Form Games (EFGs): The methods were applied to games with imperfect recall, such as the "Absent-minded Taxi Driver." The hierarchy successfully certified this game as strictly monotone at level $\ell=2$.
- Regularization: For Wichardt’s Game—a zero-sum game known to lack a Nash equilibrium in behavioral strategies—the SDP found the closest SOS-monotone version. This modified game possessed a zero symmetrized Jacobian, ensuring the existence of an equilibrium.
- Scalability: Synthetic games of degrees 4, 5, and 8 were tested. While smaller games were solved in milliseconds, a degree-8 game with 168 monomials required approximately 37 seconds, highlighting the computational trade-offs inherent in SOS optimization.
Conclusion and Future Directions
This work provides a powerful set of tools for certifying and regularizing polynomial games. By transforming intractable verification problems into solvable SDPs, it opens new avenues for applying decentralized learning in complex environments like Fisher markets and resource allocation. Future research will focus on improving scalability through "sparse" SOS techniques and extending these certificates to more general smooth functions beyond polynomials.
Summary updated