# Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 25 references that are in the map.
- First posted on arXiv 22 Dec 2024.

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

- [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)
- [No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2004.00603/) (2020)
- [Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games](https://mlsanity.com/paper/2206.15395/) (2022)
- [Efficient Algorithms for Planning with Participation Constraints](https://mlsanity.com/paper/2205.07767/) (2022)
- [Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation](https://mlsanity.com/paper/2203.07181/) (2022)
- [Computation of Stackelberg Equilibria of Finite Sequential Games](https://mlsanity.com/paper/1507.07677/) (2015)
- [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)

## Abstract (arXiv)

We study equilibrium computation with extensive-form correlation in two-player turn-taking stochastic games. Our main results are two-fold: (1) We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium (SEFCE), which runs in time polynomial in the size of the game, as well as the number of bits required to encode each input number. (2) We give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium (EFCE) up to machine precision, i.e., the algorithm achieves approximation error varepsilon in time polynomial in the size of the game, as well as log(1 / varepsilon). Our algorithm for SEFCE is the first polynomial-time algorithm for equilibrium computation with commitment in such a general class of stochastic games. Existing algorithms for SEFCE typically make stronger assumptions such as no chance moves, and are designed for extensive-form games in the less succinct tree form. Our algorithm for approximately optimal EFCE is, to our knowledge, the first algorithm that achieves 3 desiderata simultaneously: approximate optimality, polylogarithmic dependency on the approximation error, and compatibility with stochastic games in the more succinct graph form. Existing algorithms achieve at most 2 of these desiderata, often also relying on additional technical assumptions.