Computing Optimal Coarse Correlated Equilibria in Sequential Games
This addresses the challenge of equilibrium computation in game theory for scenarios with limited communication, though it is incremental as it extends existing concepts to sequential settings.
The paper tackles the problem of computing optimal coarse correlated equilibria in sequential games, showing that in two-player games without chance moves, an optimal equilibrium can be computed in polynomial time, while it is NP-hard in general multi-player games.
We investigate the computation of equilibria in extensive-form games where ex ante correlation is possible, focusing on correlated equilibria requiring the least amount of communication between the players and the mediator. Motivated by the hardness results on the computation of normal-form correlated equilibria, we introduce the notion of normal-form coarse correlated equilibrium, extending the definition of coarse correlated equilibrium to sequential games. We show that, in two-player games without chance moves, an optimal (e.g., social welfare maximizing) normal-form coarse correlated equilibrium can be computed in polynomial time, and that in general multi-player games (including two-player games with Chance), the problem is NP-hard. For the former case, we provide a polynomial-time algorithm based on the ellipsoid method and also propose a more practical one, which can be efficiently applied to problems of considerable size. Then, we discuss how our algorithm can be extended to games with Chance and games with more than two players.