Aggregate Fictitious Play for Learning in Anonymous Polymatrix Games (Extended Version)
This is an incremental improvement for multi-agent systems in game theory, addressing computational efficiency in learning scenarios.
The paper tackles the exponential growth of the joint action space in fictitious play for learning Nash equilibrium in games with unknown reward functions by introducing aggregate fictitious play (agg-FP) for anonymous polymatrix games, which reduces the action space and accelerates convergence while maintaining convergence guarantees.
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.