A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving

Luca Carminati, Federico Cacciamani, Marco Ciccone, Nicola Gatti

This paper, presented at ICML 2022, tackles a long-standing hurdle in game theory: how to efficiently solve games where a team of players coordinates against an adversary. By bridging the gap between complex team dynamics and well-understood 2-player zero-sum games, the authors unlock a suite of powerful algorithmic tools previously unavailable for team-based scenarios.

TL;DR

The authors introduce a "team-public-information" (TPI) representation that converts adversarial team games into strategically equivalent 2-player zero-sum games. This transformation enables the first use of advanced techniques like no-regret learning (CFR+), automated abstractions, and subgame solving to find optimal team strategies in large-scale environments.

What Problem Does This Paper Address?

In recent years, AI has achieved superhuman performance in 2-player zero-sum games (2p0s) like Poker and StarCraft II. These successes rely on representing the game as a tree and using tools like no-regret learning and abstractions to navigate massive strategy spaces.

However, adversarial team games (ATGs)—where a team coordinates against an opponent—are much harder. The core issue is asymmetric information: team members see different things. If you try to treat a team as a single player on a standard game tree, you lose "realization equivalence." Essentially, the team's best strategies (normal-form strategies) cannot be directly represented as simple behavioral choices on a standard tree without an exponential explosion in complexity. Because of this, computing a Team Maxmin Equilibrium with Correlation (TMEcor) is APX-hard, and the powerful tools used for 2p0s games simply don't apply.

Methods

The authors bridge this gap by introducing the Team-Public-Information (TPI) representation.

The key innovation is the introduction of a Coordinator. Instead of modeling individual team members, the TPI representation models a single coordinator who only knows information common to the entire team (public information). At each decision point, the coordinator issues a prescription: a set of instructions telling each team member what action to take for every possible private state they might be in.

Figure 1: Example of game conversion: from extensive form to team-public-information representation.

To make this practical, the authors provide an algorithm (PUBLICTEAMCONVERSION) and several optimization techniques:

  • Pruning: Removing prescriptions that lead to impossible private states.
  • Folding: Using beliefs over private states rather than explicitly sampling every chance outcome, significantly shrinking the tree.
  • Imperfect-Recall Abstractions: Merging similar subgames to further reduce the number of information sets.

Datasets

The researchers evaluated their approach using multi-player parametric versions of two standard poker benchmarks:

  • Kuhn Poker: A simplified poker game used to test game-theoretic algorithms. The authors tested versions with 2 to 3 team members and 3 to 6 card ranks.
  • Leduc Poker: A more complex variant with betting rounds and a public card. Tested versions included 2 to 3 team members, various betting limits, and up to 5 card ranks.

Key Insights and Ideas

  • Strategic Equivalence: The authors formally prove that a Nash Equilibrium in their converted TPI game is realization-equivalent to the TMEcor in the original team game. This justifies using 2p0s solvers to find optimal team strategies.
  • Explainability: The coordinator's prescriptions act as "shared team conventions." This makes the resulting AI strategies highly interpretable compared to previous black-box approaches.
  • Expressive Abstractions: The TPI tree allows for state and action abstractions that are more powerful than those possible in the original extensive-form game. They show that any abstraction in the original form can be mapped to TPI, but the reverse is not true.
  • Efficiency via Public Info: If a game has "common external information" (everyone sees the opponent's and chance's moves), the TPI tree size becomes linear relative to the original game, making it solvable in polynomial time.

Key Results

The TPI representation, combined with pruning and folding, leads to dramatic reductions in game size.

Table 1: Size of the game trees returned by the different favours of our conversion (basic, pruned, folded, imperfect-recall abstraction of folded, and lossy imperfect-recall abstraction of folded) and by the tree decomposition by Zhang & Sandholm (2022); size of the reduced normal form. We use the following notation: mnKr is Kuhn poker with a team of m players facing a team of n player and r ranks; mnLbrc is Leduc poker with a team of m players facing a team of n players, a maximum number b of bets allowed in each betting round, a number of ranks r, and a number of indistinguishable suits c). Game values are provided both for the exact case (in white) and when using our abstraction (in red). The empty cells are due to instances with more than 2 · 109 nodes or out-of-memory.
  • Compactness: In many instances (e.g., Leduc poker 21L523), the TPI representation resulted in nearly half the number of actions compared to the previous state-of-the-art tree decomposition methods.
  • Speedup: Using the "lossy" abstraction allowed the CFR+ algorithm to converge to an equilibrium up to three orders of magnitude faster than the basic TPI representation.
  • Scalability: The authors demonstrated the first successful application of no-regret learning (CFR+ and Monte Carlo CFR) to adversarial team games, showing clear convergence toward optimal strategies in reasonable timeframes.

Limitations and Future Work

While TPI is a major step forward, the authors acknowledge some limitations:

  • Worst-Case Complexity: In games with very little public information, the TPI tree can still grow exponentially.
  • Subgame Solving: While the TPI structure theoretically allows for subgame solving (refining strategies online), the auxiliary games created can be very large. Developing more efficient subgame-solving techniques specifically for TPI is a key area for future research.
  • Automated Abstractions: The current abstractions were designed manually based on game knowledge. Creating automated, domain-independent abstraction algorithms for team games remains an open challenge.

Summary updated

Abstract

\emph{Ex ante} correlation is becoming the mainstream approach for \emph{sequential adversarial team games}, where a team of players faces another team in a zero-sum game. It is known that team members' asymmetric information makes both equilibrium computation \textsf{APX}-hard and team's strategies not directly representable on the game tree. This latter issue prevents the adoption of successful tools for huge 2-player zero-sum games such as, \emph{e.g.}, abstractions, no-regret learning, and subgame solving. This work shows that we can recover from this weakness by bridging the gap between sequential adversarial team games and 2-player games. In particular, we propose a new, suitable game representation that we call \emph{team-public-information}, in which a team is represented as a single coordinator who only knows information common to the whole team and prescribes to each member an action for any possible private state. The resulting representation is highly \emph{explainable}, being a 2-player tree in which the team's strategies are behavioral with a direct interpretation and more expressive than the original extensive form when designing abstractions. Furthermore, we prove payoff equivalence of our representation, and we provide techniques that, starting directly from the extensive form, generate dramatically more compact representations without information loss. Finally, we experimentally evaluate our techniques when applied to a standard testbed, comparing their performance with the current state of the art.
BibTeX
@inproceedings{carminati2022marriage,
  author = {Luca Carminati and Federico Cacciamani and Marco Ciccone and Nicola Gatti},
  title = {{A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=KZYu5wM6pcP},
}
Figure