Nash Convergence of Gradient Dynamics in General-Sum Games

By Satinder Singh, Michael Kearns, Yishay Mansour. 2000

304 citations recorded by the source corpus.

Multi-agent games are becoming an increasingly prevalent formalism for the study of electronic commerce and auctions. The speed at which transactions can take place and the growing complexity of electronic marketplaces makes the study of computationally simple agents an appealing direction. In this work, we analyze the behavior of agents that incrementally adapt their strategy through gradient ascent on expected payoff, in the simple setting of two-player, two-action, iterated general-sum games, and present a surprising result. We show that either the agents will converge to a Nash equilibrium, or if the strategies themselves do not converge, then their average payoffs will nevertheless converge to the payoffs of a Nash equilibrium.

Subfields: Economics and Econometrics, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Unrolled Generative Adversarial Networks (2016, methodology): “ This is similar to the situation in simple matrix games like rock-paper-scissors and matching pennies, where alternating gradient descent (ascent) with a ﬁxed learning rate is known not to converge (Singh et al., 2000; Bowling & Veloso, 2002). In the unrolled case, however, this undesirable beh”
Empirically Evaluating Multiagent Learning Algorithms (2014, methodology): “GIGA-WoLF is the latest algorithm in a line of gradient learners that started with IGA (Singh et al., 2000).”
Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, background): “Most recent successes in games are based on decentralized multi-agent learning (Brown, 1951; Singh et al., 2000; Lowe et al., 2017; Silver et al., 2018), where agents compete against each other and optimize their own rewards to gradually improve their strategies.”
Multiagent Learning: Basics, Challenges, and Prospects (2012, background): “In contrast to other reinforcement learning algorithms, IGA-WoLF assumes that the agents possess a lot of information about the payoff structure.”
Continuous Adaptation via Meta-Learning in Nonstationary and Competitive Environments (2017, background): “ents is a well known issue that has been extensively studied in the context of learning in simple multi-player iterated games (such as rock-paper-scissors) where each episode is one-shot interaction (Singh et al., 2000; Bowling, 2005; Conitzer & Sandholm, 2007). In such games, discovering and co”
The Mechanics of n-Player Differentiable Games (2018, background): “Convergence to Nash equilibria in two-player games was studied in Singh et al. (2000).”
A survey and critique of multiagent deep reinforcement learning (2018, background): “We refer the interested reader to seminal works about convergence in multiagent domains [23,41,42,45,113,165,167,277,295,357,367].”
Multi-Agent Learning with Policy Prediction (2010, methodology): “Similar to the analysis in (Singh, Kearns, and Mansour 2000; Bowling and Veloso 2002), our proof of this theorem is accomplished by examining the possible cases of the dynamics of players’ strategies following IGA-PP, as done by Lemma 3, 4, and 5.”
Evolutionary Dynamics of Multi-Agent Learning: A Survey (2015, background): “It has been proven that, in two-player two-action games, IGA either converges to a Nash equilibrium, or the asymptotic expected payoff of the two players converges to the expected payoff of a Nash equilibrium (Singh et al., 2000).”
Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks (2018, methodology): “In the limit of vanishing step size, SGA approximates a continuous-time autonomous dynamical system, the asymptotic convergence of which has been established in Singh et al. [2000], Cherukuri et al. [2017], Nagarajan and Kolter [2017].”
AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents (2003, methodology): “Many of the proposed algorithms satisfy the first property (e.g. (Vrieze, 1987; Claus & Boutilier, 1998; Singh et al., 2000; Bowling & Veloso, 2002; Wang & Sandholm, 2002)).”
Probabilistic Recursive Reasoning for Multi-Agent Reinforcement Learning (2019, unknown): “that requires certain levels of intelligent reasonings between agents. We compared our algorithm with a series of baselines. In the matrix game, we compare against IGA (Inﬁnitesimal Gradient Ascent) (Singh et al., 2000). In the differential games, the baselines from multi-agent learning algorithms a”
Convergence and No-Regret in Multiagent Learning (2004, background): “Singh, Kearns, and Mansour [6] analyzed gradient ascent (IGA) in two-player, two-action games, e.”
Reaching pareto-optimality in prisoner’s dilemma using conditional joint action learning (2007, methodology): “[26] introduced and analyzed the concept of an Infinitesimal Gradient Ascent Learner (IGA) which changes its strategy in the direction of positive payoff gradient, but with an infinitesimal step size.”
Classes of Multiagent Q-learning Dynamics with epsilon-greedy Exploration (2010, methodology): “In cases where learning is equivalent to or resembles policy-gradient algorithms, researchers have found that adaptive methods tend to converge to a Nash equilibrium (Tuyls et al., 2003) or “orbit” a Nash equilibrium (Singh et al., 2000).”
Game Theory and Multi-agent Reinforcement Learning (2012, methodology): “Another gradient technique frequently studied in games is the Infinitesimal Gradient Ascent (IGA) family of algorithms (Singh et al, 2000; Bowling and Veloso, 2001; Zinkevich, 2003; Bowling, 2005).”
Theoretical Advantages of Lenient Learners: An Evolutionary Game Theoretic Perspective (2008, background): “As previously mentioned, Q-learning has certain guarantees of convergence under theoretical conditions, which include performing each action an infinite number of times in each state, as well as proper settings for the learning rate (Singh et al., 2000; Watkins and Dayan, 1992).”