  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.
