  Computational game theory has many applications in the modern world in both
adversarial situations and the optimization of social good. While there exist
many algorithms for computing solutions in two-player interactions, finding
optimal strategies in multiplayer interactions efficiently remains an open
challenge. This paper focuses on computing the multiplayer Team-Maxmin
Equilibrium with Coordination device (TMECor) in zero-sum extensive-form games.
TMECor models scenarios when a team of players coordinates ex ante against an
adversary. Such situations can be found in card games (e.g., in Bridge and
Poker), when a team works together to beat a target player but communication is
prohibited; and also in real world, e.g., in forest-protection operations, when
coordinated groups have limited contact during interdicting illegal loggers.
The existing algorithms struggle to find a TMECor efficiently because of their
high computational costs. To compute a TMECor in larger games, we make the
following key contributions: (1) we propose a hybrid-form strategy
representation for the team, which preserves the set of equilibria; (2) we
introduce a column-generation algorithm with a guaranteed finite-time
convergence in the infinite strategy space based on a novel best-response
oracle; (3) we develop an associated-representation technique for the exact
representation of the multilinear terms in the best-response oracle; and (4) we
experimentally show that our algorithm is several orders of magnitude faster
than prior state-of-the-art algorithms in large games.
