  We investigate the computation of equilibria in extensive-form games where ex
ante correlation is possible, focusing on correlated equilibria requiring the
least amount of communication between the players and the mediator. Motivated
by the hardness results on the computation of normal-form correlated
equilibria, we introduce the notion of normal-form coarse correlated
equilibrium, extending the definition of coarse correlated equilibrium to
sequential games. We show that, in two-player games without chance moves, an
optimal (e.g., social welfare maximizing) normal-form coarse correlated
equilibrium can be computed in polynomial time, and that in general
multi-player games (including two-player games with Chance), the problem is
NP-hard. For the former case, we provide a polynomial-time algorithm based on
the ellipsoid method and also propose a more practical one, which can be
efficiently applied to problems of considerable size. Then, we discuss how our
algorithm can be extended to games with Chance and games with more than two
players.
