Zero-Sum Games between Mean-Field Teams: Reachability-Based Analysis under Mean-Field Sharing

Yue Guan, Mohammad Afshari, Panagiotis TsiotrasAAAI 2024 · DOI

Abstract

This paper addresses the computational challenges of large-scale competitive multi-agent systems by introducing Zero-Sum Mean-Field Team Games (ZS-MFTGs). By modeling teams in the infinite-population limit, the authors develop a reachability-based analysis that significantly simplifies the decision space. They prove that strategies derived from this mean-field limit are robustly $\epsilon$-optimal for finite teams, with a performance gap that converges at a rate of $O(1/\sqrt{N})$. Empirical simulations on a two-node graph game validate these theoretical bounds, demonstrating a scalable approach to adversarial team dynamics that avoids the traditional curse of dimensionality.

Introduction

In multi-agent systems involving large-scale competitive teams—such as robotic swarms in a warehouse or military units on a battlefield—researchers face two massive hurdles. First, computational complexity for optimal team strategies is NEXP-complete, exploding exponentially with the number of agents. Second, traditional models often assume the opponent team is "well-behaved" or uses identical strategies. In a real zero-sum game, however, an adversary will use highly specialized, non-identical strategies to exploit weaknesses. This work seeks near-optimal strategies for large teams that are computationally efficient yet theoretically guaranteed to hold up against sophisticated, non-identical opponents.

Methodology: Reachability and Mean-Field Approximation

The researchers bridge the gap between finite-agent reality and infinite-agent theory using a Mean-Field Approximation. Instead of tracking every individual agent, they model the "mass" or distribution of the team. This transforms the game into a duel between two "fictitious coordinators" who prescribe local policies for their entire teams based on observed state distributions.

To make dynamic programming feasible, the authors employ Reachability-Based Analysis. Rather than searching the massive space of all possible policies, they focus on the reachable sets—the actual state distributions a team can realistically achieve. Lipschitz assumptions on dynamics and rewards ensure that the game's value remains stable under small changes in agent distributions.

Figure 3: Visualization of the game value surfaces and reachable sets at different time steps, illustrating the gap between max-min and min-max values.

Key Insights

A major finding is that restricting a team to identical strategies (where all agents follow the same rule) is "good enough." This simplified strategy remains nearly optimal even when the opponent is allowed to give every single one of their agents a unique, specialized task. Furthermore, the paper demonstrates that in discrete settings, a perfect Nash Equilibrium may not exist (where max-min and min-max values meet). This highlights why focusing on lower and upper game values is more practical for real-world engineering than chasing a perfect equilibrium.

Results and Empirical Validation

The authors established a formal sub-optimality bound: the performance loss when moving from the theoretical infinite model to a real finite team of size $N$ is at most $O(1/\sqrt{N})$.

Figure 4: Empirical validation of the theoretical $O(1/\sqrt{N})$ convergence rate, showing the sub-optimality gap decreasing as the number of agents increases.

In numerical experiments involving a two-node graph game, the "sub-optimality gap" followed the predicted $1/\sqrt{N}$ curve almost perfectly. This approach successfully avoids the curse of dimensionality, allowing for the analysis of teams that would be impossible to solve using traditional multi-agent reinforcement learning or control theory.

Limitations and Future Work

While the current work focuses on discrete state and action spaces, extending this to continuous spaces (like fluid dynamics) is a logical next step. The authors also suggest that future work should investigate heterogeneous sub-populations (e.g., teams consisting of both tanks and infantry) and more restrictive information structures where "Mean-Field Sharing" is not fully available. Additionally, they aim to investigate the Linear-Quadratic-Gaussian (LQG) setup, a staple in control engineering.

Summary updated

BibTeX
@inproceedings{guan2024zero,
  author = {Yue Guan and Mohammad Afshari and Panagiotis Tsiotras},
  title = {{Zero-Sum Games between Mean-Field Teams: Reachability-Based Analysis under Mean-Field Sharing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28831},
}
Figure