# Paths to Equilibrium in Games

arXiv: https://arxiv.org/abs/2403.18079 · HTML: https://mlsanity.com/paper/2403.18079/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 18 of its 54 references that are in the map.
- First posted on arXiv 26 Mar 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 18 of 18)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [A Practical Guide to Multi-Objective Reinforcement Learning and Planning](https://mlsanity.com/paper/2103.09568/) (2021)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [On Gradient-Based Learning in Continuous Games](https://mlsanity.com/paper/1804.05464/) (2018)
- [Decentralized Q-Learning for Stochastic Teams and Games](https://mlsanity.com/paper/1506.07924/) (2015)
- [Adversarial Example Games](https://mlsanity.com/paper/2007.00720/) (2020)
- [Fictitious play in zero-sum stochastic games](https://mlsanity.com/paper/2010.04223/) (2020)
- [Nash Convergence of Gradient Dynamics in Iterated General-Sum Games](https://mlsanity.com/paper/1301.3892/) (2013)
- [Decentralized Learning for Optimality in Stochastic Dynamic Teams and Games with Local Control and Global State Information](https://mlsanity.com/paper/1903.05812/) (2019)
- [Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspective](https://mlsanity.com/paper/2212.08791/) (2022)
- [Best-Response Dynamics and Fictitious Play in Identical-Interest and Zero-Sum Stochastic Games](https://mlsanity.com/paper/2111.04317/) (2021)
- [Fictitious Play in Markov Games with Single Controller](https://mlsanity.com/paper/2205.11389/) (2022)
- [Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/2110.04638/) (2021)
- [Nash Equilibria and Pitfalls of Adversarial Training in Adversarial Robustness Games](https://mlsanity.com/paper/2210.12606/) (2022)
- [Distributed Inertial Best-Response Dynamics](https://mlsanity.com/paper/1605.00601/) (2016)

## Built on by (most cited first, 1 of 1)

- [Grouped Satisficing Paths in Pure Strategy Games: a Topological Perspective](https://mlsanity.com/paper/2509.23157/) (2025)

## Abstract (arXiv)

In multi-agent reinforcement learning (MARL) and game theory, agents repeatedly interact and revise their strategies as new data arrives, producing a sequence of strategy profiles. This paper studies sequences of strategies satisfying a pairwise constraint inspired by policy updating in reinforcement learning, where an agent who is best responding in one period does not switch its strategy in the next period. This constraint merely requires that optimizing agents do not switch strategies, but does not constrain the non-optimizing agents in any way, and thus allows for exploration. Sequences with this property are called satisficing paths, and arise naturally in many MARL algorithms. A fundamental question about strategic dynamics is such: for a given game and initial strategy profile, is it always possible to construct a satisficing path that terminates at an equilibrium? The resolution of this question has implications about the capabilities or limitations of a class of MARL algorithms. We answer this question in the affirmative for normal-form games. Our analysis reveals a counterintuitive insight that reward deteriorating strategic updates are key to driving play to equilibrium along a satisficing path.