Research map / Learning theory and algorithms / Submodular and game algorithms
Team-Maxmin Equilibrium: Efficiency Bounds and Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Coordinate team actions rather than require independent execution | Team-maxmin equilibrium · General n-player games | Price of Uncorrelation: m^{n-2} | Helped |
| Use the correlated strategy's first-player marginal and uniform strategies over other players' supported actions | Reconstruction from correlated strategies · General n-player games | utility guarantee: at least \frac{v}{m^{n-2}} | Helped |
| Initialize IteratedLP with uniform strategies for every team member (ablation) | IteratedLP · General n-player games | worst-case approximation factor: \frac{1}{m^{n-1}} to \frac{1}{m^{n-2}} | Helped |
| Initialize IteratedLP with pure strategies (ablation) | IteratedLP · General n-player games | worst-case approximation factor: 0 | Hurt |
| Use global optimization with BARON | Team-maxmin equilibrium computation · RandomGames | lower bound / upper bound: larger than 0.7 | Helped |
| Increase the number of actions per player | Team-maxmin approximation algorithms · RandomGames | approximation quality | Mixed |
| Increase the number of players | Reconstruction from correlated strategies · RandomGames | ratio to BARON lower bound: larger than 0.6; with n=3, larger than 0.8 | Hurt |
| Use more random restarts (ablation) | IteratedLP · RandomGames | solution quality | Mixed |
| Replace BARON with IteratedLP | Team-maxmin equilibrium computation · RandomGames | approximation quality | Hurt |
| Use support enumeration with ε<1 (ablation) | Support enumeration · RandomGames | termination / scalability: m≤20 with n=3; m=5 with n∈{4,5} | Hurt |
Closest papers by meaning
- Computing Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games (AAAI 2020 · similarity 0.92)
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.89)
- Team-Fictitious Play for Reaching Team-Nash Equilibrium in Multi-team Games (NeurIPS 2024 · similarity 0.89)
- Zero-Sum Games between Mean-Field Teams: Reachability-Based Analysis under Mean-Field Sharing (AAAI 2024 · similarity 0.87)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.87)
- The Complexity of Two-Team Polymatrix Games with Independent Adversaries (ICLR 2025 · similarity 0.87)
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.