# Safe Subgame Resolving for Extensive Form Correlated Equilibrium

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

## Key facts

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

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

- [Human-Level Performance in No-Press Diplomacy via Equilibrium Search](https://mlsanity.com/paper/2010.02923/) (2020)
- [Improving Policies via Search in Cooperative Partially Observable Games](https://mlsanity.com/paper/1912.02318/) (2019)
- [Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks](https://mlsanity.com/paper/1905.12564/) (2019)
- [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games](https://mlsanity.com/paper/2102.06973/) (2021)
- [Subgame solving without common knowledge](https://mlsanity.com/paper/2106.06068/) (2021)
- [Efficient Regret Minimization Algorithm for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/1910.12450/) (2019)
- [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)
- [Safe Search for Stackelberg Equilibria in Extensive-Form Games](https://mlsanity.com/paper/2102.01775/) (2021)

## Abstract (arXiv)

Correlated Equilibrium is a solution concept that is more general than Nash Equilibrium (NE) and can lead to outcomes with better social welfare. However, its natural extension to the sequential setting, the textitExtensive Form Correlated Equilibrium (EFCE), requires a quadratic amount of space to solve, even in restricted settings without randomness in nature. To alleviate these concerns, we apply textitsubgame resolving, a technique extremely successful in finding NE in zero-sum games to solving general-sum EFCEs. Subgame resolving refines a correlation plan in an textitonline manner: instead of solving for the full game upfront, it only solves for strategies in subgames that are reached in actual play, resulting in significant computational gains. In this paper, we (i) lay out the foundations to quantify the quality of a refined strategy, in terms of the textitsocial welfare and textitexploitability of correlation plans, (ii) show that EFCEs possess a sufficient amount of independence between subgames to perform resolving efficiently, and (iii) provide two algorithms for resolving, one using linear programming and the other based on regret minimization. Both methods guarantee textitsafety, i.e., they will never be counterproductive. Our methods are the first time an online method has been applied to the correlated, general-sum setting.