Research map / Learning theory and algorithms / Submodular and game algorithms

DAG-Based Column Generation for Adversarial Team Games

ICML 2024 · Learning theory and algorithms › Submodular and game algorithms · approach: Equilibrium solvers for adversarial games

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes DCG, a column generation algorithm over the TB-DAG form that computes a pure coordinated best response in the original game tree and transforms it into TB-DAG form, achieving large speedups for computing TMECor in adversarial team games.

Problem

Computing a team-maxmin equilibrium with coordination device (TMECor) in sequential adversarial team games is hard because the team's coordinated strategy space is exponential in game size; existing CG and TB-DAG methods each scale poorly in large games.

Approach

Run column generation over the compact TB-DAG representation, but compute the best response in the original game tree using a new pure best-response oracle based on a correlation plan over relevant joint sequences (polynomial-size constraints), then transform that pure best response into TB-DAG form at each iteration.

Key results

• DCGpure is at least two orders of magnitude faster than state-of-the-art baselines in large games with deep and wide game trees (e.g., Leduc 3-3L1-13: 40s vs 485s for CGlinrelax_random; many baselines exceed 10h or run out of memory).
• DCG requires significantly fewer iterations than normal-form CG (e.g., 82 vs 1149 iterations for CGpure on Leduc 3-3L1-13 at 1e-6 precision).
• Theoretically, DCG converges in at most O*((b(p+1))^w) iterations, exponentially faster than normal-form CG in the worst case; the transformed TB-DAG for a pure best response has size O(|H∪Z|).

Measured effects reported in the paper

Surprising findings

• Normal-form CG algorithms with a single oracle are fastest on shallow game trees, and the DAG-based linear program is fastest on very narrow trees, so DCG is not uniformly best.
• The randomized-strategy variants of DCG and relaxed-BRO variants perform worse than the pure-BRO DCG in wide games because the transformation of randomized best responses is costly.

Limitations

• Baseline runtimes differ from prior papers due to different settings; the authors re-implemented all baselines, and the baseline code is not publicly available.
• DCG may run out of memory or be slower than normal-form CG in games with shallow trees due to per-iteration transformation cost.
• Experiments are limited to Kuhn and Leduc poker variants; the approach has not been scaled to very large games.

Experimental setup

Datasets: Kuhn poker Leduc poker

Benchmarks: Kuhn poker (n-player variants) Leduc poker (n-player variants)

Metrics: runtime (s) number of iterations to convergence target precision of team value (1e-6)

Baselines: CGrandom CG2random CGpure DAG CGdag DCGrandom DCG2random

Builds on: TB-DAG sequence-form double oracle von Stengel-Forges polytope normal-form column generation (Zhang et al. 2021; Farina et al. 2021) policy-space response oracles

Closest papers by meaning

• Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.84)
• Open Ad Hoc Teamwork with Cooperative Game Theory (ICML 2024 · similarity 0.83)
• Team-Fictitious Play for Reaching Team-Nash Equilibrium in Multi-team Games (NeurIPS 2024 · similarity 0.82)
• Equilibrium Policy Generalization: A Reinforcement Learning Framework for Cross-Graph Zero-Shot Generalization in Pursuit-Evasion Games (NeurIPS 2025 · similarity 0.82)
• Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size (AAAI 2025 · similarity 0.82)
• FightLadder: A Benchmark for Competitive Multi-Agent Reinforcement Learning (ICML 2024 · similarity 0.82)