Fixed-Parameter Algorithms for Optimal Correlation in General-Sum Extensive-Form Games
March 23, 2022 (GHC 8102)

Abstract: Computing optimal correlated equilibria of various notions in extensive-form games is NP-hard in the general case, but known to be easy in certain cases, perhaps most notably zero-sum games and normal-form games. In this talk, we will bridge the gap between the NP-hardness result and the cases known to be easy, by developing fixed-parameter algorithms for correlated equilibria. In particular, we will discuss two different but closely-related problems.

First, for adversarial team games, we develop a representation of the strategy space of a team of players who all have the same objective. Our representation has size bounded by a parameter that is related to the information structure of the game; when the parameter is constant, we thus recover a polynomial-time algorithm. It leads to algorithms based on both linear programming and regret minimization for solving zero-sum adversarial team games.

Next, we extend our representation to be able to handle correlated equilibria in general-sum games. As we will show, this is a more complex setting than adversarial team games---indeed, under reasonable complexity assumptions, it is impossible to match the team game bounds in general-sum games. However, our representation technique still works with some modifications, and we obtain fixed-parameter complexity bounds under a different parameterization.

In experiments, we show that our technique enables solving larger games than previous techniques, especially when the parameter is small.

Based on joint work with Gabriele Farina, Andrea Celli, and Tuomas Sandholm.