Coarse Correlation in Extensive-Form Games


  • Gabriele Farina Carnegie Mellon University
  • Tommaso Bianchi Politecnico di Milano
  • Tuomas Sandholm Carnegie Mellon University



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.




How to Cite

Farina, G., Bianchi, T., & Sandholm, T. (2020). Coarse Correlation in Extensive-Form Games. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1934-1941.



AAAI Technical Track: Game Theory and Economic Paradigms