Computing Optimal Coarse Correlated Equilibria in Sequential Games

  • 2019-01-18 13:32:52
  • Andrea Celli, Stefano Coniglio, Nicola Gatti
  • 2

Abstract

We investigate the computation of equilibria in extensive-form games where exante correlation is possible, focusing on correlated equilibria requiring theleast amount of communication between the players and the mediator. Motivatedby the hardness results on the computation of normal-form correlatedequilibria, we introduce the notion of normal-form coarse correlatedequilibrium, extending the definition of coarse correlated equilibrium tosequential games. We show that, in two-player games without chance moves, anoptimal (e.g., social welfare maximizing) normal-form coarse correlatedequilibrium can be computed in polynomial time, and that in generalmulti-player games (including two-player games with Chance), the problem isNP-hard. For the former case, we provide a polynomial-time algorithm based onthe ellipsoid method and also propose a more practical one, which can beefficiently applied to problems of considerable size. Then, we discuss how ouralgorithm can be extended to games with Chance and games with more than twoplayers.

 

Quick Read (beta)

loading the full paper ...