Research map / Multi-agent systems and games / Games and equilibria
Zero-Sum Games between Mean-Field Teams: Reachability-Based Analysis under Mean-Field Sharing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Models two large competing teams as a discrete zero-sum mean-field team game, reduces the infinite-population limit to a zero-sum game between two coordinators solved by reachability-based dynamic programming, and proves the resulting identical-strategy policy is O(N^-0.5)-optimal in the finite-population game.
Problem
Competitive team-vs-team games with many agents per team are computationally intractable (NEXP-hard in general), and the opponent team's strategies cannot be assumed identical without justification.
Approach
Approximate the finite-population zero-sum team game by its infinite-population mean-field limit, convert it into a zero-sum game between two fictitious coordinators via common information, and solve it with a reachability-set dynamic program over mean-field distributions; show that the resulting identical team strategy remains near-optimal even when the opponent uses non-identical strategies.
Key results
- Theorem 3 shows the identical Blue strategy from the coordinator game is O(1/sqrt(N))-optimal (N = min team size) in the finite-population game, even against non-identical Red strategies.
- Numerical Example 2 shows a non-identical deterministic Blue strategy with 3 agents achieves worst-case value -ν0(y1) - 0.016ν0(y2) versus -ν0(y1) - 0.518ν0(y2) for the best identical mixed strategy.
- Numerical Example 1 shows the coordinator game lower and upper values differ at t=0 (0.5298 vs 0.5384), so no Nash equilibrium exists in that instance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a non-identical deterministic split instead of the identical mixed strategy | Blue team in Example 2 with three agents · Example 2, Red transition from y2 to y1 at t=1 | transition probability: 0.518 -> 0.016 | Helped |
| Use the infinite-population optimal coordination strategy in the finite-population game | Blue team strategy · Finite-population zero-sum mean-field team games | suboptimality gap: O(N −0.5) | Mixed |
| Use the reachability-based coordinator formulation | Example 1 coordinator game · Example 1, coordinator game at t=0 | game value: 0.5298 vs. 0.5384 | Mixed |
Surprising findings
- The coordinator game value may not exist (lower and upper values differ), contrary to continuous-setting results.
- Identical mixed team strategies can be substantially outperformed by non-identical deterministic strategies in small finite populations.
Limitations
- Results rely on Lipschitz continuity assumptions on dynamics and rewards (Assumptions 1-2), and a discontinuous example shows the approximation can fail without them.
- Analysis is restricted to finite-horizon, discrete state and action spaces with two-state examples for numerics.
- Coordinator game value may not exist, so only single-sided (lower/upper) optimality is established.
Experimental setup
Benchmarks: two-node graph toy ZS-MFTG examples
Metrics: game value suboptimality gap vs number of agents
Baselines: mean-field equilibrium (MFE) identical mixed team strategy
Builds on: mean-field team problem (Arabneydi and Mahajan 2014) mean-field games (Lasry and Lions 2007) common-information approach (Nayyar, Mahajan, Teneketzis 2013)
Closest papers by meaning
- Team-Fictitious Play for Reaching Team-Nash Equilibrium in Multi-team Games (NeurIPS 2024 · similarity 0.89)
- Learning Large-Scale Competitive Team Behaviors with Mean-Field Interactions (NeurIPS 2026 · similarity 0.88)
- Team-Maxmin Equilibrium: Efficiency Bounds and Algorithms (AAAI 2017 · similarity 0.87)
- Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis (NeurIPS 2025 · similarity 0.85)
- The Complexity of Two-Team Polymatrix Games with Independent Adversaries (ICLR 2025 · similarity 0.84)
- Bench-MFG: A Benchmark Suite for Learning in Stationary Mean Field Games (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.