Computing optimal ex ante correlated equilibria in two-player sequential games

We investigate the computation of equilibria in extensive-form games when ex ante correlation is possible, focusing on correlated equilibria requiring the least amount of communication between the players and the mediator. Motivated by hardness results on normal-form correlated equilibria, we investigate whether it is pos- sible to compute normal-form coarse correlated equilibria efficiently. We show that an optimal (e.g., social welfare maximizing) normal- form coarse correlated equilibrium can be computed in polynomial time in two-player games without chance moves, and that in gen- eral multi-player games (including two-player games with chance) the problem is NP-hard. For the two-player case, we provide both a polynomial-time algorithm based on the ellipsoid method and a column generation algorithm based on the simplex method which can be efficiently applied in practice. We also show that the pric- ing oracle employed in the column generation procedure can be extended to games with two players and chance.