# Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2022.

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

- [Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation](https://mlsanity.com/paper/2203.07181/) (2022)
- [Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem](https://mlsanity.com/paper/2410.05673/) (2024)
- [Imperfect-Recall Games: Equilibrium Concepts and Their Complexity](https://mlsanity.com/paper/2406.15970/) (2024)
- [GraphChase: A Platform and Benchmark for Urban Network Security Games](https://mlsanity.com/paper/2501.17559/) (2025)
- [Decision Making under Imperfect Recall: Algorithms and Benchmarks](https://mlsanity.com/paper/2602.15252/) (2026)

## Abstract (arXiv)

A classic result in the theory of extensive-form games asserts that the set of strategies available to any perfect-recall player is strategically equivalent to a low-dimensional convex polytope, called the sequence-form polytope. Online convex optimization tools operating on this polytope are the current state-of-the-art for computing several notions of equilibria in games, and have been crucial in landmark applications of computational game theory. However, when optimizing over the joint strategy space of a team of players, one cannot use the sequence form to obtain a strategically-equivalent convex description of the strategy set of the team. In this paper, we provide new complexity results on the computation of optimal strategies for teams, and propose a new representation, coined team belief DAG (TB-DAG), that describes team strategies as a convex set. The TB-DAG enjoys state-of-the-art parameterized complexity bounds, while at the same time enjoying the advantages of efficient regret minimization techniques. We show that TB-DAG can be exponentially smaller and can be computed exponentially faster than all other known representations, and that the converse is never true. Experimentally, we show that the TB-DAG, when paired with learning techniques, yields state of the art on a wide variety of benchmark team games.