  While Nash equilibrium in extensive-form games is well understood, very
little is known about the properties of extensive-form correlated equilibrium
(EFCE), both from a behavioral and from a computational point of view. In this
setting, the strategic behavior of players is complemented by an external
device that privately recommends moves to agents as the game progresses;
players are free to deviate at any time, but will then not receive future
recommendations. Our contributions are threefold. First, we show that an EFCE
can be formulated as the solution to a bilinear saddle-point problem. To
showcase how this novel formulation can inspire new algorithms to compute
EFCEs, we propose a simple subgradient descent method which exploits this
formulation and structural properties of EFCEs. Our method has better
scalability than the prior approach based on linear programming. Second, we
propose two benchmark games, which we hope will serve as the basis for future
evaluation of EFCE solvers. These games were chosen so as to cover two natural
application domains for EFCE: conflict resolution via a mediator, and
bargaining and negotiation. Third, we document the qualitative behavior of EFCE
in our proposed games. We show that the social-welfare-maximizing equilibria in
these games are highly nontrivial and exhibit surprisingly subtle sequential
behavior that so far has not received attention in the literature.
