# Multiagent Evaluation under Incomplete Information

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

## Key facts

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

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

- [Scaling Scaling Laws with Board Games](https://mlsanity.com/paper/2104.03113/) (2021)
- [Towards a Standardised Performance Evaluation Protocol for Cooperative MARL](https://mlsanity.com/paper/2209.10485/) (2022)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)
- [Estimating α-Rank by Maximizing Information Gain](https://mlsanity.com/paper/2101.09178/) (2021)
- [Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games](https://mlsanity.com/paper/2207.08426/) (2022)
- [Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons](https://mlsanity.com/paper/2110.04136/) (2021)
- [Game Theoretic Rating in N-player general-sum games with Equilibria](https://mlsanity.com/paper/2210.02205/) (2022)
- [Learning to Identify Top Elo Ratings: A Dueling Bandits Approach](https://mlsanity.com/paper/2201.04480/) (2022)
- [Composing Efficient, Robust Tests for Policy Selection](https://mlsanity.com/paper/2306.07372/) (2023)
- [Swim till You Sink: Computing the Limit of a Game](https://mlsanity.com/paper/2408.11146/) (2024)
- [AREG: Adversarial Resource Extraction Game for Evaluating Persuasion and Resistance in Large Language Models](https://mlsanity.com/paper/2602.16639/) (2026)
- [Beyond the high score: Prosocial ability profiles of multi-agent populations](https://mlsanity.com/paper/2509.14485/) (2025)
- [Efficient Nash Equilibrium Computation for Cybersecurity Games](https://mlsanity.com/paper/2609.19399/) (2026)

## Abstract (arXiv)

This paper investigates the evaluation of learned multiagent strategies in the incomplete information setting, which plays a critical role in ranking and training of agents. Traditionally, researchers have relied on Elo ratings for this purpose, with recent works also using methods based on Nash equilibria. Unfortunately, Elo is unable to handle intransitive agent interactions, and other techniques are restricted to zero-sum, two-player settings or are limited by the fact that the Nash equilibrium is intractable to compute. Recently, a ranking method called α-Rank, relying on a new graph-based game-theoretic solution concept, was shown to tractably apply to general games. However, evaluations based on Elo or α-Rank typically assume noise-free game outcomes, despite the data often being collected from noisy simulations, making this assumption unrealistic in practice. This paper investigates multiagent evaluation in the incomplete information regime, involving general-sum many-player games with noisy outcomes. We derive sample complexity guarantees required to confidently rank agents in this setting. We propose adaptive algorithms for accurate ranking, provide correctness and sample complexity guarantees, then introduce a means of connecting uncertainties in noisy match outcomes to uncertainties in rankings. We evaluate the performance of these approaches in several domains, including Bernoulli games, a soccer meta-game, and Kuhn poker.