Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
Brian H. Zhang, Gabriele Farina, Andrea Celli, Tuomas Sandholm
Abstract
We study the problem of finding
optimal correlated equilibria of various sorts:
normal-form coarse correlated equilibrium (NFCCE),
extensive-form coarse correlated equilibrium (EFCCE), and
extensive-form correlated equilibrium (EFCE). This is NP-hard in the general case and has been studied in special cases, most notably
triangle-free games (Farina and Sandholm, 2020), which include all two-player games with public chance moves. However, the general case is not well understood, and algorithms usually scale poorly. In this paper, we make two primary contributions.
First, we introduce the
correlation DAG, a representation of the space of correlated strategies whose structure and size are dependent on the specific solution concept desired. It extends the
team belief DAG of Zhang, Farina, and Sandholm (2022) to general-sum games. For each of the three solution concepts, its size depends exponentially only on a parameter related to the information structure of the game. We also prove a fundamental complexity gap: while our size bounds for NFCCE are similar to those achieved in the case of team games by Zhang, Farina, and Sandholm (2022), this is impossible to achieve for the other two concepts under standard complexity assumptions.
Second, we propose a
two-sided column generation approach to compute optimal correlated strategies in extensive-form games. Our algorithm improves upon the
one-sided approach of Farina, Celli, Gatti, and Sandholm (2021) by means of a new decomposition of correlated strategies which allows players to re-optimize their sequence-form strategies with respect to correlation plans which were previously added to the support.
Experiments show that our techniques outperform the prior state of the art for computing optimal general-sum correlated equilibria, and that our two families of approaches have complementary strengths: the correlation DAG is fast when the parameter is small and the two-sided column generation approach is superior when the parameter is large. For team games, we show that the two-sided column generation approach vastly outperforms standard column generation approaches, making it the state of the art algorithm when the parameter is large. % Along the way, we also introduce two new benchmark games: a
trick-taking game that emulates the endgame phase of the card game
bridge, and a
ride-sharing game, where two drivers traversing a graph are competing to reach specific nodes and serve requests.
Bibtex entry
@inproceedings{Zhang22:Optimal,
title={Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation},
author={Brian H. Zhang and Gabriele Farina and Andrea Celli and Tuomas Sandholm and Andrea Celli and Tuomas Sandholm},
booktitle={Economics and Computation},
year={2022}
}