# Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation

arXiv: https://arxiv.org/abs/2203.07181 · HTML: https://mlsanity.com/paper/2203.07181/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 72 references that are in the map.
- First posted on arXiv 14 Mar 2022.

## Builds on (most cited first, 13 of 13)

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks](https://mlsanity.com/paper/1905.12564/) (2019)
- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [Online Convex Optimization for Sequential Decision Processes and Extensive-Form Games](https://mlsanity.com/paper/1809.03075/) (2018)
- [Computational Results for Extensive-Form Adversarial Team Games](https://mlsanity.com/paper/1711.06930/) (2017)
- [No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2004.00603/) (2020)
- [Coarse Correlation in Extensive-Form Games](https://mlsanity.com/paper/1908.09893/) (2019)
- [Timeability of Extensive-Form Games](https://mlsanity.com/paper/1502.03430/) (2015)
- [Team Correlated Equilibria in Zero-Sum Extensive-Form Games via Tree Decompositions](https://mlsanity.com/paper/2109.05284/) (2021)
- [Efficient Regret Minimization Algorithm for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/1910.12450/) (2019)
- [Computing Ex Ante Coordinated Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games](https://mlsanity.com/paper/2009.12629/) (2020)
- [Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization](https://mlsanity.com/paper/2202.00789/) (2022)
- [Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond](https://mlsanity.com/paper/2009.04336/) (2020)

## Built on by (most cited first, 5 of 5)

- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Policy Optimization finds Nash Equilibrium in Regularized General-Sum LQ Games](https://mlsanity.com/paper/2404.00045/) (2024)
- [GraphChase: A Platform and Benchmark for Urban Network Security Games](https://mlsanity.com/paper/2501.17559/) (2025)
- [Barriers to Welfare Maximization with No-Regret Learning](https://mlsanity.com/paper/2411.01720/) (2024)
- [Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation](https://mlsanity.com/paper/2412.16934/) (2024)

## Abstract (arXiv)

We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse correlated equilibrium (EFCCE), and extensive-form correlated equilibrium (EFCE). We make two primary contributions. First, we introduce a new algorithm for computing optimal equilibria in all three notions. Its runtime depends exponentially only on a parameter related to the information structure of the game. We also prove a fundamental complexity gap: while our size bounds for NFCCE are similar to those achieved in the case of team games by Zhang et al., this is impossible to achieve for the other two concepts under standard complexity assumptions. Second, we propose a two-sided column generation approach for use when the runtime or memory usage of the previous algorithm is prohibitive. Our algorithm improves upon the one-sided approach of Farina et al. by means of a new decomposition of correlated strategies which allows players to re-optimize their sequence-form strategies with respect to correlation plans which were previously added to the support. Experiments show that our techniques outperform the prior state of the art for computing optimal general-sum correlated equilibria.