Research map / Multi-agent systems and games / Games and equilibria
Team-Fictitious Play for Reaching Team-Nash Equilibrium in Multi-team Games
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.
Introduces Team-FP, a fictitious-play variant with inertia and last-action responses for team members, and proves it reaches epsilon-near Team-Nash equilibrium in zero-sum potential team games, extended to multi-team Markov games.
Problem
Whether teams of self-interested agents can reach Team-Nash equilibrium (TNE) in multi-team games, where team members coordinate a joint best response against other teams without communication.
Approach
Modifies fictitious play so each agent responds to the last actions of its team members and to beliefs about opponent teams, with inertia in action updates (log-linear-style), enabling implicit team coordination; convergence is analysed via a frozen-belief reference scenario, optimal coupling, and stochastic differential inclusions.
Key results
- Team-FP reaches near-TNE in ZSPTGs with the team-Nash gap bounded by tau log|A| asymptotically (almost surely).
- Explicit coordination (group size 4) converges fastest, followed by group size 2, then independent Team-FP; SFP and MWU fail to reach team coordination in simulations.
- Smaller temperature tau yields lower final team-Nash gap; larger delta speeds independent Team-FP convergence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Team-FP instead of smooth fictitious play or multiplicative weights update | Two-team ZSPTG · Two-team ZSPTG | team-Nash gap | Helped |
| Use fully coordinated teams rather than groups of two or independent agents (ablation) | Team-FP · Two-team ZSPTG with four agents per team | convergence speed | Helped |
| Use groups of two rather than independent agents (ablation) | Team-FP · Two-team ZSPTG with four agents per team | convergence speed | Helped |
| Compete against stationary opponents rather than opponents also using Team-FP | Team-FP · Three-team ZSPTG | convergence speed | Helped |
| Decrease the temperature parameter \tau (ablation) | Team-FP · Three-team ZSPTG | team-Nash gap: 0.1, 0.15, 0.2 | Helped |
| Increase the independent action-update probability from 0.2 to 0.5 (ablation) | Independent Team-FP · Three-team ZSPTG | convergence speed: 0.2; 0.5 | Helped |
| Increase the independent action-update probability too much (ablation) | Independent Team-FP · Multi-team ZSPTG | team coordination | Hurt |
Surprising findings
- Standard smoothed FP and multiplicative weights fail to reach team-coordinated near-TNE, even though the average joint actions of teams can under Team-FP.
Limitations
- Asymptotic almost-sure convergence only; no convergence rate guarantees.
- Analysis restricted to zero-sum potential team games; beyond-ZSPTG and Markov game results are only numerical.
- Assumes homogeneous beliefs among opponents' agents.
Experimental setup
Benchmarks: randomly generated ZSPTG simulations airport security game
Metrics: team-Nash gap
Baselines: smoothed fictitious play multiplicative weights update explicit team coordination (group size 2 and 4) stationary opponent
Builds on: fictitious play log-linear learning smoothed fictitious play multiplicative weights update
Closest papers by meaning
- Team Correlated Equilibria in Zero-Sum Extensive-Form Games via Tree Decompositions (AAAI 2022 · similarity 0.89)
- Efficiently Computing Nash Equilibria in Adversarial Team Markov Games (ICLR 2023 · similarity 0.89)
- Team-Maxmin Equilibrium: Efficiency Bounds and Algorithms (AAAI 2017 · similarity 0.89)
- Zero-Sum Games between Mean-Field Teams: Reachability-Based Analysis under Mean-Field Sharing (AAAI 2024 · similarity 0.89)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.87)
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.86)
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.