STON'R Converges to First-Order Nash~Equilibria of Multiplayer Games
2026-06-08 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study complicated multiplayer games where standard strategies like perfect or local Nash equilibria might not exist or are very hard to find. They focus on a broader solution called first-order Nash equilibria (FONE), which covers many cases previously studied. Building on earlier work with an algorithm named STON'R, they show it reliably finds these FONE solutions in general multiplayer games with smooth utilities. Their results help unify different equilibrium ideas and they test the algorithm successfully on known game examples.
Nonconcave gamesNash equilibriumLocal Nash equilibriumFirst-order Nash equilibriumVariational inequalityGeneral-sum gamesSTON'R algorithmSmooth utility functionsPPAD-hardMultiplayer games
Authors
Marika Kosohorská, Tomáš Kroupa, Tomáš Votroubek
Abstract
Nonconcave games present a unique challenge, as neither pure Nash equilibria nor local Nash equilibria (LNE) are guaranteed to exist, even in zero-sum settings. Additionally, computing approximate LNE in smooth multiplayer games over bounded regions is PPAD-hard. These challenges, coupled with the inherent complexity, have driven recent research toward broader equilibrium concepts, such as min-max critical points, and first-order Nash equilibria (FONE), which correspond to solutions of specific non-monotone variational inequalities. This paper addresses general-sum multiplayer games with compact convex strategy sets and smooth, nonconcave utility functions. Daskalakis et al. introduced the STON'R algorithm for solving variational inequality problems and established convergence under smoothness assumptions. They further showed that the algorithm's limit points correspond to equilibria in specific classes of games, namely local minimax equilibria in two-player zero-sum games and Nash equilibria in smooth concave games. In this work, we extend the convergence result to multiplayer general-sum games and show that the variational inequality solutions targeted by STON'R correspond to first-order Nash equilibria (FONE), a general game-theoretic solution concept that unifies these previously studied cases. We demonstrate the effectiveness and robustness of the algorithm on various examples from recent literature.