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 possible to compute normal-form coarse correlated equilibria efficiently. We show that an optimal (e.g., social welfare maximizing) normalform coarse correlated equilibrium can be computed in polynomial time in two-player games without chance moves, and that in general 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 pricing oracle employed in the column generation procedure can be extended to games with two players and chance.