Coarse Correlation in Extensive-Form Games

Gabriele Farina, Tommaso Bianchi, Tuomas Sandholm

---

Abstract

Coarse correlation models strategic interactions of rational agents complemented by a correlation device which is a mediator that can recommend behavior but not enforce it. Despite being a classical concept in the theory of normal-form games since 1978, not much is known about the merits of coarse correlation in extensive-form settings. In this paper, we consider two instantiations of the idea of coarse correlation in extensive-form games: normal-form coarse-correlated equilibrium (NFCCE), already defined in the literature, and extensive-form coarse-correlated equilibrium (EFCCE), a new solution concept that we introduce. We show that EFCCEs are a subset of NFCCEs and a superset of the related extensive-form correlated equilibria. We also show that, in $n$-player extensive-form games, social-welfare-maximizing EFCCEs and NFCCEs are bilinear saddle points, and give new efficient algorithms for the special case of two-player games with no chance moves. Experimentally, our proposed algorithm for NFCCE is two to four orders of magnitude faster than the prior state of the art.

---

Bibtex entry

@inproceedings{Farina20:Coarse, title={Coarse Correlation in Extensive-Form Games}, author={Farina, Gabriele and Bianchi, Tommaso and Sandholm, Tuomas}, booktitle={AAAI Conference on Artificial Intelligence}, year={2020} }