Approximating Nash Equilibria in General-Sum Games via Meta-Learning
This addresses the challenge of finding Nash equilibria in complex games for AI and game theory applications, though it is incremental as it builds on existing regret minimization techniques.
The paper tackled the problem of approximating Nash equilibria in general-sum games, which is computationally intractable, by using meta-learning to reduce correlations in strategies from regret minimizers, resulting in significantly better approximations than state-of-the-art methods.
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.