Multiagent Learning in Large Anonymous Games

Ian A. Kash, Eric J. Friedman, Joseph Y. Halpern

Abstract

In massive distributed systems, simplicity often outperforms complexity. This paper demonstrates that a straightforward stage learning algorithm—where agents periodically update their strategies based on observed average rewards—efficiently converges to Nash equilibria in large anonymous games. Counterintuitively, the "Law of Large Numbers" makes learning more robust as the number of agents increases, allowing systems with millions of users to reach stable states where smaller groups remain chaotic.

Introduction: The Scaling Challenge

Multiagent learning is notoriously difficult to scale. As the number of players increases, the complexity of interactions typically explodes, and the information required for an agent to track the system becomes overwhelming. Traditional algorithms often have convergence times that scale poorly with the population size, making them impractical for large-scale distributed systems like peer-to-peer networks or global auctions.

Furthermore, real-world systems are inherently noisy, with agents making mistakes or experiencing network delays. This research addresses the challenge of finding a learning algorithm that is scalable, robust to noise, and requires minimal information.

Methodology: Stage Learning in Anonymous Games

The authors focus on Large Anonymous Games, where an agent’s payoff depends on the aggregate behavior of the population (e.g., how many people are using a resource) rather than the identities of individual actors. This is a hallmark of systems like traffic routing or file sharing.

The proposed Stage Learning algorithm operates in cycles:

  1. Stages: Time is divided into discrete blocks.
  2. Fixed Strategy + Exploration: During a stage, an agent mostly plays one fixed strategy but occasionally explores other options at random.
  3. The Pivot: At the end of the stage, the agent calculates which action yielded the highest average reward and adopts that as their strategy for the next stage.

The paper provides a theoretical proof (Theorem 3.5) showing that if "best-reply dynamics" converge in a game, then a system of stage learners will also converge to an approximate Nash equilibrium in a finite number of stages, regardless of the total number of agents.

Experimental Setup

The algorithm was evaluated in several simulated environments:

  • Contribution Games: Agents decide how much effort to contribute to a collective project.
  • Congestion Games: Modeling network traffic or resource usage.
  • Classic Dilemmas: Prisoner’s Dilemma and "Climbing" games.
  • Diamond-type Search Models: Testing specific payoff structures.

Results and Discussion

The primary insight of this work is the "More is Better" Paradox. In many AI fields, more agents mean more complexity. Here, the Law of Large Numbers works in the learner's favor. With a large population, the "noise" of individual mistakes averages out, creating a stable statistical environment that makes it easier for an individual agent to learn the optimal response.

Convergence of stage learning vs. no-regret algorithms. Stage learning (solid/dashed lines) achieves a closer proximity to equilibrium than no-regret methods (dotted lines).

As shown in Figure 1, stage learning algorithms (Stage 10, Stage 100) reach a "higher quality" equilibrium—closer to the true Nash equilibrium—than standard no-regret algorithms. While no-regret methods converge, they often get stuck in near-optimal noisy states, whereas stage learning's periodic "pivoting" allows it to settle into more precise strategies.

The 'More is Better' Paradox: Large populations (Stage 100) exhibit stable convergence, while small populations (Stage 2) remain chaotic.

The robustness of the approach is further illustrated in Figure 2. In simulations of contribution games, populations of 100 agents (Stage 100) converged to equilibrium strategies almost immediately. In contrast, groups of only 2 agents (Stage 2) remained "chaotic" due to the high impact of individual mistakes on the aggregate environment. This demonstrates that providing agents with simple statistical information about the population can speed up convergence by an order of magnitude.

Conclusion and Future Work

Stage learning provides a scalable and robust framework for multiagent systems. By leveraging the statistical stability of large populations, it avoids the complexity traps of traditional learning methods. However, the current model relies on the assumption that best-reply dynamics converge and focuses on stateless games. Future research will explore extending these techniques to games with state (e.g., where agents have varying levels of resources) and developing defenses against malicious (Byzantine) actors who might attempt to subvert the learning process.

Summary updated

BibTeX
@inproceedings{kash2009multiagent,
  author = {Ian A. Kash and Eric J. Friedman and Joseph Y. Halpern},
  title = {{Multiagent Learning in Large Anonymous Games}},
  booktitle = {AAMAS},
  year = {2009},
}
Figure