# Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 51 references that are in the map.
- First posted on arXiv 17 Oct 2023.

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

- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- ["Other-Play" for Zero-Shot Coordination](https://mlsanity.com/paper/2003.02979/) (2020)
- [The Hanabi Challenge: A New Frontier for AI Research](https://mlsanity.com/paper/1902.00506/) (2019)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning](https://mlsanity.com/paper/2206.15378/) (2022)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning](https://mlsanity.com/paper/2210.05492/) (2022)
- [No Press Diplomacy: Modeling Multi-Agent Gameplay](https://mlsanity.com/paper/1909.02128/) (2019)
- [DREAM: Deep Regret minimization with Advantage baselines and Model-free learning](https://mlsanity.com/paper/2006.10410/) (2020)
- [No-Press Diplomacy from Scratch](https://mlsanity.com/paper/2110.02924/) (2021)
- [Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks](https://mlsanity.com/paper/1905.12564/) (2019)
- [Hindsight and Sequential Rationality of Correlated Play](https://mlsanity.com/paper/2012.05874/) (2020)
- [Graphical Models for Game Theory](https://mlsanity.com/paper/1301.2281/) (2013)
- [Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers](https://mlsanity.com/paper/2106.09435/) (2021)
- [No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2004.00603/) (2020)
- [Coarse Correlation in Extensive-Form Games](https://mlsanity.com/paper/1908.09893/) (2019)
- [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games](https://mlsanity.com/paper/2102.06973/) (2021)
- [Learning to Correlate in Multi-Player General-Sum Sequential Games](https://mlsanity.com/paper/1910.06228/) (2019)
- [Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions](https://mlsanity.com/paper/2008.00540/) (2020)
- [Symmetric Decomposition of Asymmetric Games](https://mlsanity.com/paper/1711.05074/) (2017)
- [On the Convergence of Fictitious Play: A Decomposition Approach](https://mlsanity.com/paper/2205.01469/) (2022)

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

- [Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank](https://mlsanity.com/paper/2410.01101/) (2024)
- [Approximating Nash Equilibria in General-Sum Games via Meta-Learning](https://mlsanity.com/paper/2504.18868/) (2025)
- [Projected Exploitability Descent for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games](https://mlsanity.com/paper/2606.29169/) (2026)

## Abstract (arXiv)

Self-play is a technique for machine learning in multi-agent systems where a learning algorithm learns by interacting with copies of itself. Self-play is useful for generating large quantities of data for learning, but has the drawback that the agents the learner will face post-training may have dramatically different behavior than the learner came to expect by interacting with itself. For the special case of two-player constant-sum games, self-play that reaches Nash equilibrium is guaranteed to produce strategies that perform well against any post-training opponent; however, no such guarantee exists for multiplayer games. We show that in games that approximately decompose into a set of two-player constant-sum games (called constant-sum polymatrix games) where global ε-Nash equilibria are boundedly far from Nash equilibria in each subgame (called subgame stability), any no-external-regret algorithm that learns by self-play will produce a strategy with bounded vulnerability. For the first time, our results identify a structural property of multiplayer games that enable performance guarantees for the strategies produced by a broad class of self-play algorithms. We demonstrate our findings through experiments on Leduc poker.