Timezone: »

 
Poster
Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks
Gabriele Farina · Chun Kai Ling · Fei Fang · Tuomas Sandholm

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #221
in Theory -- Game Theory and Computational Economics »

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.

Keywords: Game Theory and Computational Economics · Theory
[ Paper]  [ Slides] 

Author Information

Gabriele Farina (Carnegie Mellon University)
Chun Kai Ling (Carnegie Mellon University)
Fei Fang (Carnegie Mellon University)
Tuomas Sandholm (CMU, Strategic Machine, Strategy Robot, Optimized Markets)

More from the Same Authors