Approximating Nash Equilibria in General-Sum Games via Meta-Learning
David Sychrovský, Christopher Solinas, Revan MacQueen, Kevin Wang, James R. Wright, Nathan R. Sturtevant, Michael Bowling · 2025
Read Approximating Nash Equilibria in General-Sum Games via Meta-Learning by David Sychrovský, Christopher Solinas, Revan MacQueen, Kevin Wang, James R. Wright, Nathan R. Sturtevant, Michael Bowling (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18868.txt.
Introduction
David Sychrovsky and co-authors use meta-learning to approximate Nash equilibria in general-sum games in a 2025 game theory paper. A Nash equilibrium assigns each player a strategy that gives no one a reason to deviate alone. Finding one in general-sum games is believed to be intractable in the worst case, despite always existing.
Regret minimization works well for two-player zero-sum games but loses its guarantees in general-sum settings with several players. The authors train a meta-learner to produce good approximations faster across many different games. Practical equilibrium finders matter for economics, security planning, and multi-agent AI systems that must settle on stable joint behavior.
Catalog record
| CREATOR | David Sychrovský, Christopher Solinas, Revan MacQueen, Kevin Wang, James R. Wright, Nathan R. Sturtevant, Michael Bowling |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18868
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Approximating Nash Equilibria in General-Sum Games via Meta-Learning David Sychrovský, Christopher Solinas, Revan MacQueen, Kevin Wang, James R. Wright, Nathan R. Sturtevant, Michael Bowling Abstract Nash equilibrium is perhaps the best-known solution concept in game theory. Such a solution assigns a strategy to each player which offers no incentive to unilaterally deviate. While a Nash equilibrium is guaranteed to always exist, the problem of finding one in general-sum games is PPAD-complete, generally considered intractable. Regret minimization is an efficient framework for approximating Nash equilibria in two-player zero-sum games. However, in general-sum games, such algorithms are only guaranteed to converge to a coarse-correlated equilibrium (CCE), a solution concept where players can correlate their strategies. In this work, we use meta-learning to minimize the correlations in strategies produced by a regret minimizer. This encourages the regret minimizer to find strategies that are closer to a Nash equilibrium. The meta-learned regret minimizer is still guaranteed to converge to a CCE, but we give a bound on the distance to Nash equilibrium in terms of our meta-loss. We evaluate our approach in general-sum imperfect information games. Our algorithms provide significantly better approximations of Nash equilibria than state-of-the-art regret minimization techniques. 1 Introduction The Nash equilibrium is one of the most influential solution concepts in game theory. A strategy profile is a Nash equilibrium if it has the guarantee that no player can benefit by unilaterally deviating from it. The robustness of this guarantee means that Nash equilibria have applications in many domains ranging from economics ( Vickrey, 1961 ; Milgrom and Weber, 1982 ) to machine learning ( Goodfellow et al., 2014 ) . Finding an efficient algorithm for computing Nash equilibria has attracted much attention ( Rosenthal, 1973 ; Monderer and Shapley, 1996 ; Kearns et al., 2001 ; Cai and Daskalakis, 2011 ; Littman and Stone, 2005 ) . However, it was shown that, in its full generality, finding a Nash equilibrium is PPAD-complete ( Papadimitriou, 1994 ; Daskalakis et al., 2009a ) . Many related decision problems, such as ‘Is a given action in the support of a Nash equilibrium?’, are NP-complete ( Gilboa and Zemel, 1989 ) . Despite these negative results, computing Nash equilibria in special classes of games, in particular two-player zero-sum games, is tractable. In this setting, regret minimization has become the dominant approach for finding Nash equilibria ( Nisan et al., 2007 ) . This framework casts each player as an independent online learner who repeatedly interacts with the game, selecting strategies according to dynamics that lead to sublinear growth of their accumulated regret . Regret minimizers guarantee convergence to Nash equilibria in two-player zero-sum games, and are the basis for many significant results in imperfect information games ( Bowling et al., 2015 ; Moravčik et al., 2017 ; Brown and Sandholm, 2018 ; Brown et al., 2020 ; Brown and Sandholm, 2019c ; Schmid et al., 2023 ) . Outside the two-player zero-sum setting, regret minimization algorithms are no longer guaranteed to converge to a Nash equilibrium. Instead, a regret minimizer’s empirical distribution of play converges to a coarse-correlated equilibrium (CCE) ( Hannan, 1957 ; Hart and Mas-Colell, 2000 ) . The CCE is a relaxed equilibrium concept, which gives a distribution over the outcomes of the game such that it isn’t beneficial for any player to deviate from it. If this distribution is uncorrelated, meaning it can be expressed as a profile of independent strategies, it is also a Nash equilibrium. As such, Nash equilibria form a subset of CCEs, for which the outcome distribution can be marginalized into strategies of the individual players. The degree to which a CCE is correlated, or how much a player can infer about the actions of other players given their action, can be formalized by total correlation ( Watanabe, 1960 ) . A recently proposed learning not to regret framework allows one to meta-learn a regret minimizer to optimize a specified objective, while keeping regret minimization guarantees ( Sychrovský et al., 2024 ) . Their goal was to accelerate the empirical convergence rate on a distribution of black-box tasks. In this work, we meta-learn predictions that optimize an alternative meta-objective: minimizing correlation in the players’ strategies. The resulting algorithm is still guaranteed to converge to a CCE, and is meta-learned to empirically converge to a Nash equilibrium on a distribution of interest. If the support of the distribution doesn’t include all general-sum games, the problem of finding Nash may be tractable even if P \neq PPAD. We further show this approach is sound by providing a bound on the distance to a Nash equilibrium in terms of our meta-objective. We evaluate our approach in general-sum imperfect information games. Our algorithms provide significantly better approximations of Nash equilibria than state-of-the-art regret minimization techniques. 1.1 Related Work The Nash equilibrium is one of the oldest solution concepts in game theory. Thanks to its many appealing properties, developing efficient algorithms for approximating Nash equilibria has seen much attention ( Kontogiannis et al., 2009 ; Daskalakis et al., 2009b ; Daskalakis et al., 2007 ; Bosse et al., 2010 ; Deligkas et al., 2023 ; Li et al., 2024 ) . Furthermore, it was shown that, unless P = NP, polynomial algorithms for finding all Nash equilibria cannot exist ( Gilboa and Zemel, 1989 ) . This negative result suggests that there are games for which finding a Nash equilibrium requires enumerating all possible strategies — an amount exponential in the number of actions. The Lemke-Howson algorithm ( Lemke and Howson, 1964 ) is one such algorithm, which provably finds a Nash equilibrium of two-player general-sum games in normal-form. It works by constructing a path on an abstract polyhedron, which is guaranteed to terminate at the Nash equilibrium. Similar to the simplex method ( Murty, 1984 ) , the path may be exponentially long in some games. However, such games are empirically rare ( Codenotti et al., 2008 ) . Several modifications of the Lemke-Howson algorithm were proposed to improve its empirical performance ( Codenotti et al., 2008 ; Gatti et al., 2012 ) . However, the algorithm cannot work with games in extensive-form. When converted to normal-form, the size of the game increases exponentially, making these algorithms scale very poorly. Regret minimization is a powerful framework for online convex optimization ( Zinkevich, 2003 ; Nisan et al., 2007 ) , with regret matching as one of the most popular algorithms in game applications ( Hart and Mas-Colell, 2000 ) . Counterfactual regret minimization enables the use of regret matching in sequential decision-making, by decomposing the full regret to individual states ( Zinkevich et al., 2007 ) . In two-player zero-sum games, regret minimization algorithms are guaranteed to converge to a Nash equilibrium. Many prior works explored modifications of regret matching to speed up its empirical performance in two-player zero-sum games, such as CFR + ( Tammelin, 2014 ) , Linear CFR ( Brown et al., 2019 ) , PCFR + ( Farina et al., 2023 ) , Discounted CFR ( Brown and Sandholm, 2019a ) , and their hyperparameter-scheduled counterparts ( Zhang et al., 2024 ) . Despite the lack of theoretical guarantees in general-sum games, regret minimization algorithms empirically