# Aggregate Fictitious Play for Learning in Anonymous Polymatrix Games (Extended Version)

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 30 references that are in the map.
- First posted on arXiv 26 Aug 2025.

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

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Learning in Mean Field Games: A Survey](https://mlsanity.com/paper/2205.12944/) (2022)
- [Fictitious play in zero-sum stochastic games](https://mlsanity.com/paper/2010.04223/) (2020)
- [Independent Learning in Stochastic Games](https://mlsanity.com/paper/2111.11743/) (2021)
- [Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Path](https://mlsanity.com/paper/2208.11639/) (2022)
- [Notions of Anonymity, Fairness and Symmetry for Finite Strategic-Form Games](https://mlsanity.com/paper/1311.4766/) (2013)
- [Differential Equation Approximations for Population Games using Elementary Probability](https://mlsanity.com/paper/2312.07598/) (2023)
- [Generalized Individual Q-learning for Polymatrix Games with Partial Observations](https://mlsanity.com/paper/2409.02663/) (2024)

## Abstract (arXiv)

Fictitious play (FP) is a well-studied algorithm that enables agents to learn Nash equilibrium in games with certain reward structures. However, when agents have no prior knowledge of the reward functions, FP faces a major challenge: the joint action space grows exponentially with the number of agents, which slows down reward exploration. Anonymous games offer a structure that mitigates this issue. In these games, the rewards depend only on the actions taken; not on who is taking which action. Under such a structure, we introduce aggregate fictitious play (agg-FP), a variant of FP where each agent tracks the frequency of the number of other agents playing each action, rather than these agents' individual actions. We show that in anonymous polymatrix games, agg-FP converges to a Nash equilibrium under the same conditions as classical FP. In essence, by aggregating the agents' actions, we reduce the action space without losing the convergence guarantees. Using simulations, we provide empirical evidence on how this reduction accelerates convergence.