# αα-Rank: Practically Scaling α-Rank through Stochastic Optimisation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2019.

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

- [Modelling Behavioural Diversity for Learning in Open-Ended Games](https://mlsanity.com/paper/2103.07927/) (2021)
- [MALib: A Parallel Framework for Population-based Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2106.07551/) (2021)
- [Online Double Oracle](https://mlsanity.com/paper/2103.07780/) (2021)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [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)
- [Estimating α-Rank by Maximizing Information Gain](https://mlsanity.com/paper/2101.09178/) (2021)
- [Neural Auto-Curricula](https://mlsanity.com/paper/2106.02745/) (2021)
- [Learning to Identify Top Elo Ratings: A Dueling Bandits Approach](https://mlsanity.com/paper/2201.04480/) (2022)
- [Self-adaptive PSRO: Towards an Automatic Population-based Game Solver](https://mlsanity.com/paper/2404.11144/) (2024)

## Abstract (arXiv)

Recently, α-Rank, a graph-based algorithm, has been proposed as a solution to ranking joint policy profiles in large scale multi-agent systems. α-Rank claimed tractability through a polynomial time implementation with respect to the total number of pure strategy profiles. Here, we note that inputs to the algorithm were not clearly specified in the original presentation; as such, we deem complexity claims as not grounded, and conjecture solving α-Rank is NP-hard. The authors of α-Rank suggested that the input to α-Rank can be an exponentially-sized payoff matrix; a claim promised to be clarified in subsequent manuscripts. Even though α-Rank exhibits a polynomial-time solution with respect to such an input, we further reflect additional critical problems. We demonstrate that due to the need of constructing an exponentially large Markov chain, α-Rank is infeasible beyond a small finite number of agents. We ground these claims by adopting amount of dollars spent as a non-refutable evaluation metric. Realising such scalability issue, we present a stochastic implementation of α-Rank with a double oracle mechanism allowing for reductions in joint strategy spaces. Our method, αα-Rank, does not need to save exponentially-large transition matrix, and can terminate early under required precision. Although theoretically our method exhibits similar worst-case complexity guarantees compared to α-Rank, it allows us, for the first time, to practically conduct large-scale multi-agent evaluations. On 104 × 104 random matrices, we achieve 1000x speed reduction. Furthermore, we also show successful results on large joint strategy profiles with a maximum size in the order of O(225) (≈ 33 million joint strategies) -- a setting not evaluable using α-Rank with reasonable computational budget.