# Team-maxmin equilibrium: efficiency bounds and algorithms

arXiv: https://arxiv.org/abs/1611.06134 · HTML: https://mlsanity.com/paper/1611.06134/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2016.

## Built on by (most cited first, 9 of 9)

- [A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving](https://mlsanity.com/paper/2206.09161/) (2022)
- [Efficiently Computing Nash Equilibria in Adversarial Team Markov Games](https://mlsanity.com/paper/2208.02204/) (2022)
- [Public Information Representation for Adversarial Team Games](https://mlsanity.com/paper/2201.10377/) (2022)
- [Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies](https://mlsanity.com/paper/2102.05026/) (2021)
- [GraphChase: A Platform and Benchmark for Urban Network Security Games](https://mlsanity.com/paper/2501.17559/) (2025)
- [Towards convergence to Nash equilibria in two-team zero-sum games](https://mlsanity.com/paper/2111.04178/) (2021)
- [Computing Ex Ante Equilibrium in Heterogeneous Zero-Sum Team Games](https://mlsanity.com/paper/2410.01575/) (2024)
- [Dynamic Homophily with Imperfect Recall: Modeling Resilience in Adversarial Networks](https://mlsanity.com/paper/2512.12332/) (2025)
- [Decision Making under Imperfect Recall: Algorithms and Benchmarks](https://mlsanity.com/paper/2602.15252/) (2026)

## Abstract (arXiv)

The Team-maxmin equilibrium prescribes the optimal strategies for a team of rational players sharing the same goal and without the capability of correlating their strategies in strategic games against an adversary. This solution concept can capture situations in which an agent controls multiple resources-corresponding to the team members-that cannot communicate. It is known that such equilibrium always exists and it is unique (unless degeneracy) and these properties make it a credible solution concept to be used in real-world applications, especially in security scenarios. Nevertheless, to the best of our knowledge, the Team-maxmin equilibrium is almost completely unexplored in the literature. In this paper, we investigate bounds of (in)efficiency of the Team-maxmin equilibrium w.r.t. the Nash equilibria and w.r.t. the Maxmin equilibrium when the team members can play correlated strategies. Furthermore, we study a number of algorithms to find and/or approximate an equilibrium, discussing their theoretical guarantees and evaluating their performance by using a standard testbed of game instances.