Research map / Learning theory and algorithms / Submodular and game algorithms
Connecting Optimal Ex-Ante Collusion in Teams to Extensive-Form Correlation: Faster Algorithms and Positive Complexity Results
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| cap the number of semi-randomized correlation plans at n=2 instead of n=1 (Goofspiel 3-rank) (ablation) | TMECor with semi-randomized plans · Goofspiel [E] (O=1) | team expected utility: 0.2389 -> 0.2534 | Helped |
| allowing more than 1 semi-randomized plan (n=2 or 3) versus only one (ablation) | TMECor support size · Kuhn poker [C] (O=1) | team expected utility: 0.0470 (n=1) -> 0.0655 (n=2) -> 0.0663 (n=3) -> 0.0664 (n=∞) | Helped |
| regret-based seeding of the column-generation master LP (m=1000 CFR+ iterations vs none) (ablation) | column-generation TMECor solver · Liar's dice [F] (O=3) | runtime: 4m 03s -> 1m 12s (~3.4x) | Helped |
| column generation with linear-relaxation pricing and seeding (proposed) vs prior CG-18 and FTP | TMECor computation · Liar's dice [F], Goofspiel [E], Leduc [H] | runtime: Liar's dice 1m12s vs >6h for baselines | Helped |
| solve TMECor on Liar's dice 4-faces [G] with column generation | column generation TMECor · Liar's dice [G] | completion within 6h | No clear effect |
| Goofspiel is triangle-free so the von Stengel-Forges polytope equals the correlation plan polytope, enabling polynomial-time TMECor | TMECor LP · Goofspiel | complexity | Helped |
Closest papers by meaning
- Ex ante coordination and collusion in zero-sum multi-player extensive-form games (NeurIPS 2018 · similarity 0.91)
- Computing Ex Ante Coordinated Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games (AAAI 2021 · similarity 0.91)
- Team Correlated Equilibria in Zero-Sum Extensive-Form Games via Tree Decompositions (AAAI 2022 · similarity 0.90)
- Computing Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games (AAAI 2020 · similarity 0.89)
- Team-Fictitious Play for Reaching Team-Nash Equilibrium in Multi-team Games (NeurIPS 2024 · similarity 0.86)
- Zero-Sum Games between Mean-Field Teams: Reachability-Based Analysis under Mean-Field Sharing (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.