  Coarse correlation models strategic interactions of rational agents
complemented by a correlation device, that is a mediator that can recommend
behavior but not enforce it. Despite being a classical concept in the theory of
normal-form games for more than forty years, 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), which we
introduce for the first time. We show that EFCCE is a subset of NFCCE and a
superset of the related extensive-form correlated equilibrium. We also show
that, in two-player extensive-form games, social-welfare-maximizing EFCCEs and
NFCEEs are bilinear saddle points, and give new efficient algorithms for the
special case of games with no chance moves. In our experiments, our proposed
algorithm for NFCCE is two to four orders of magnitude faster than the prior
state of the art.
