# On the Convergence of Fictitious Play: A Decomposition Approach

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 65 references that are in the map.
- First posted on arXiv 3 May 2022.

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

- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [Game-Theoretic Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00583/) (2020)
- [A Generalized Training Approach for Multiagent Learning](https://mlsanity.com/paper/1909.12823/) (2019)
- [Modelling Behavioural Diversity for Learning in Open-Ended Games](https://mlsanity.com/paper/2103.07927/) (2021)
- [Learning in Nonzero-Sum Stochastic Games with Potentials](https://mlsanity.com/paper/2103.09284/) (2021)
- [On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games](https://mlsanity.com/paper/2109.01795/) (2021)
- [Online Double Oracle](https://mlsanity.com/paper/2103.07780/) (2021)
- [Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games](https://mlsanity.com/paper/2106.04958/) (2021)
- [A Survey of Game Theoretic Approaches for Adversarial Machine Learning in Cybersecurity Tasks](https://mlsanity.com/paper/1912.02258/) (2019)
- [Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions](https://mlsanity.com/paper/2008.00540/) (2020)
- [Strategic Decompositions of Normal Form Games: Zero-sum Games and Potential Games](https://mlsanity.com/paper/1602.06648/) (2016)
- [Payoff Performance of Fictitious Play](https://mlsanity.com/paper/1308.4049/) (2013)
- [Symmetric Decomposition of Asymmetric Games](https://mlsanity.com/paper/1711.05074/) (2017)

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

- [Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability](https://mlsanity.com/paper/2310.11518/) (2023)
- [On the Geometry of Games and their Solvers](https://mlsanity.com/paper/2605.29919/) (2026)

## Abstract (arXiv)

Fictitious play (FP) is one of the most fundamental game-theoretical learning frameworks for computing Nash equilibrium in n-player games, which builds the foundation for modern multi-agent learning algorithms. Although FP has provable convergence guarantees on zero-sum games and potential games, many real-world problems are often a mixture of both and the convergence property of FP has not been fully studied yet. In this paper, we extend the convergence results of FP to the combinations of such games and beyond. Specifically, we derive new conditions for FP to converge by leveraging game decomposition techniques. We further develop a linear relationship unifying cooperation and competition in the sense that these two classes of games are mutually transferable. Finally, we analyze a non-convergent example of FP, the Shapley game, and develop sufficient conditions for FP to converge.