# Grouped Satisficing Paths in Pure Strategy Games: a Topological Perspective

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 27 Sep 2025.

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

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [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)
- [Decentralized Q-Learning for Stochastic Teams and Games](https://mlsanity.com/paper/1506.07924/) (2015)
- [Nash Convergence of Gradient Dynamics in Iterated General-Sum Games](https://mlsanity.com/paper/1301.3892/) (2013)
- [Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspective](https://mlsanity.com/paper/2212.08791/) (2022)
- [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)
- [Distributed Inertial Best-Response Dynamics](https://mlsanity.com/paper/1605.00601/) (2016)
- [On the Global Convergence of Stochastic Fictitious Play in Stochastic Games with Turn-based Controllers](https://mlsanity.com/paper/2204.01382/) (2022)
- [Paths to Equilibrium in Games](https://mlsanity.com/paper/2403.18079/) (2024)

## Abstract (arXiv)

In game theory and multi-agent reinforcement learning (MARL), each agent selects a strategy, interacts with the environment and other agents, and subsequently updates its strategy based on the received payoff. This process generates a sequence of joint strategies (st)t ≥ 0, where st represents the strategy profile of all agents at time step t. A widely adopted principle in MARL algorithms is "win-stay, lose-shift", which dictates that an agent retains its current strategy if it achieves the best response. This principle exhibits a fixed-point property when the joint strategy has become an equilibrium. The sequence of joint strategies under this principle is referred to as a satisficing path, a concept first introduced in [40] and explored in the context of N-player games in [39]. A fundamental question arises regarding this principle: Under what conditions does every initial joint strategy s admit a finite-length satisficing path (st)0 ≤ t ≤ T where s0=s and sT is an equilibrium? This paper establishes a sufficient condition for such a property, and demonstrates that any finite-state Markov game, as well as any N-player game, guarantees the existence of a finite-length satisficing path from an arbitrary initial strategy to some equilibrium. These results provide a stronger theoretical foundation for the design of MARL algorithms.