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.
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.
- 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