# Learning to Correlate in Multi-Player General-Sum Sequential Games

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2019.

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

- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers](https://mlsanity.com/paper/2106.09435/) (2021)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games](https://mlsanity.com/paper/2103.04539/) (2021)
- [Decision Making in Monopoly using a Hybrid Deep Reinforcement Learning Approach](https://mlsanity.com/paper/2103.00683/) (2021)
- [Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies](https://mlsanity.com/paper/2102.05026/) (2021)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability](https://mlsanity.com/paper/2310.11518/) (2023)
- [Integrated Decision Making and Trajectory Planning for Autonomous Driving Under Multimodal Uncertainties: A Bayesian Game Approach](https://mlsanity.com/paper/2409.13993/) (2024)

## Abstract (arXiv)

In the context of multi-player, general-sum games, there is an increasing interest in solution concepts modeling some form of communication among players, since they can lead to socially better outcomes with respect to Nash equilibria, and may be reached through learning dynamics in a decentralized fashion. In this paper, we focus on coarse correlated equilibria (CCEs) in sequential games. First, we complete the picture on the complexity of finding social-welfare-maximizing CCEs by showing that the problem is not in Poly-APX unless P = NP. Furthermore, simple arguments show that CFR - working with behavioral strategies - may not converge to a CCE. However, we devise a simple variant (CFR-S) which provably converges to the set of CCEs, but may be empirically inefficient. Thus, we design a variant of the CFR algorithm (called CFR-Jr) which approaches the set of CCEs with a regret bound sub-linear in the size of the game, and is shown to be dramatically faster than CFR-S and the state-of-the-art algorithms to compute CCEs.