# α-Rank: Multi-Agent Evaluation by Evolution

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2019.

## Built on by (most cited first, 30 of 51)

- [Towards a Standardised Performance Evaluation Protocol for Cooperative MARL](https://mlsanity.com/paper/2209.10485/) (2022)
- [Modelling Behavioural Diversity for Learning in Open-Ended Games](https://mlsanity.com/paper/2103.07927/) (2021)
- [Scaling Laws for a Multi-Agent Reinforcement Learning Model](https://mlsanity.com/paper/2210.00849/) (2022)
- [A Survey on Self-play Methods in Reinforcement Learning](https://mlsanity.com/paper/2408.01072/) (2024)
- [MALib: A Parallel Framework for Population-based Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2106.07551/) (2021)
- [On the Limitations of Elo: Real-World Games, are Transitive, not Additive](https://mlsanity.com/paper/2206.12301/) (2022)
- [Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers](https://mlsanity.com/paper/2106.09435/) (2021)
- [Online Double Oracle](https://mlsanity.com/paper/2103.07780/) (2021)
- [Evolving Diverse Red-team Language Models in Multi-round Multi-agent Games](https://mlsanity.com/paper/2310.00322/) (2023)
- [A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers](https://mlsanity.com/paper/2110.15105/) (2021)
- [Alternating Mirror Descent for Constrained Min-Max Games](https://mlsanity.com/paper/2206.04160/) (2022)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [Designing Long-term Group Fair Policies in Dynamical Systems](https://mlsanity.com/paper/2311.12447/) (2023)
- [Efficient Policy Space Response Oracles](https://mlsanity.com/paper/2202.00633/) (2022)
- [A Game-Theoretic Approach to Multi-Agent Trust Region Optimization](https://mlsanity.com/paper/2106.06828/) (2021)
- [Learning Correlated Equilibria in Mean-Field Games](https://mlsanity.com/paper/2208.10138/) (2022)
- [Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning](https://mlsanity.com/paper/2302.00797/) (2023)
- [Estimating α-Rank by Maximizing Information Gain](https://mlsanity.com/paper/2101.09178/) (2021)
- [Neural Population Learning beyond Symmetric Zero-sum Games](https://mlsanity.com/paper/2401.05133/) (2024)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [The Replicator Dynamic, Chain Components and the Response Graph](https://mlsanity.com/paper/2209.15230/) (2022)
- [Game Theoretic Rating in N-player general-sum games with Equilibria](https://mlsanity.com/paper/2210.02205/) (2022)
- [VGC-Bench: Towards Mastering Diverse Team Strategies in Competitive Pok'emon](https://mlsanity.com/paper/2506.10326/) (2025)
- [First-Order Problem Solving through Neural MCTS based Reinforcement Learning](https://mlsanity.com/paper/2101.04167/) (2021)
- [Evolutionary Dynamics and Phi-Regret Minimization in Games](https://mlsanity.com/paper/2106.14668/) (2021)
- [Learning to Identify Top Elo Ratings: A Dueling Bandits Approach](https://mlsanity.com/paper/2201.04480/) (2022)
- [Developing, Evaluating and Scaling Learning Agents in Multi-Agent Environments](https://mlsanity.com/paper/2209.10958/) (2022)
- [Fusion-PSRO: Nash Policy Fusion for Policy Space Response Oracles](https://mlsanity.com/paper/2405.21027/) (2024)
- [Is Elo Rating Reliable? A Study Under Model Misspecification](https://mlsanity.com/paper/2502.10985/) (2025)

## Abstract (arXiv)

We introduce α-Rank, a principled evolutionary dynamics methodology for the evaluation and ranking of agents in large-scale multi-agent interactions, grounded in a novel dynamical game-theoretic solution concept called Markov-Conley chains (MCCs). The approach leverages continuous- and discrete-time evolutionary dynamical systems applied to empirical games, and scales tractably in the number of agents, the type of interactions, and the type of empirical games (symmetric and asymmetric). Current models are fundamentally limited in one or more of these dimensions and are not guaranteed to converge to the desired game-theoretic solution concept (typically the Nash equilibrium). α-Rank provides a ranking over the set of agents under evaluation and provides insights into their strengths, weaknesses, and long-term dynamics. This is a consequence of the links we establish to the MCC solution concept when the underlying evolutionary model's ranking-intensity parameter, α, is chosen to be large, which exactly forms the basis of α-Rank. In contrast to the Nash equilibrium, which is a static concept based on fixed points, MCCs are a dynamical solution concept based on the Markov chain formalism, Conley's Fundamental Theorem of Dynamical Systems, and the core ingredients of dynamical systems: fixed points, recurrent sets, periodic orbits, and limit cycles. α-Rank runs in polynomial time with respect to the total number of pure strategy profiles, whereas computing a Nash equilibrium for a general-sum game is known to be intractable. We introduce proofs that not only provide a unifying perspective of existing continuous- and discrete-time evolutionary evaluation models, but also reveal the formal underpinnings of the α-Rank methodology. We empirically validate the method in several domains including AlphaGo, AlphaZero, MuJoCo Soccer, and Poker.