  Unlike normal-form games, where correlated equilibria have been studied for
more than 45 years, extensive-form correlation is still generally not well
understood. Part of the reason for this gap is that the sequential nature of
extensive-form games allows for a richness of behaviors and incentives that are
not possible in normal-form settings. This richness translates to a
significantly different complexity landscape surrounding extensive-form
correlated equilibria. As of today, it is known that finding an optimal
extensive-form correlated equilibrium (EFCE), extensive-form coarse correlated
equilibrium (EFCCE), or normal-form coarse correlated equilibrium (NFCCE) in a
two-player extensive-form game is computationally tractable when the game does
not include chance moves, and intractable when the game involves chance moves.
In this paper we significantly refine this complexity threshold by showing
that, in two-player games, an optimal correlated equilibrium can be computed in
polynomial time, provided that a certain condition is satisfied. We show that
the condition holds, for example, when all chance moves are public, that is,
both players observe all chance moves. This implies that an optimal EFCE, EFCCE
and NFCCE can be computed in polynomial time in the game size in two-player
games with public chance moves, providing the biggest positive complexity
result surrounding extensive-form correlation in more than a decade.
