Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation
This work addresses equilibrium computation for game theory and AI applications, offering the first polynomial-time SEFCE algorithm for a general class of stochastic games and the first EFCE algorithm achieving three key desiderata simultaneously, representing a significant advance over prior methods.
The paper tackles equilibrium computation in two-player turn-taking stochastic games with extensive-form correlation, presenting a polynomial-time algorithm for computing Stackelberg extensive-form correlated equilibrium (SEFCE) and an efficient algorithm for approximating optimal extensive-form correlated equilibrium (EFCE) up to machine precision with polylogarithmic dependency on error.
We study equilibrium computation with extensive-form correlation in two-player turn-taking stochastic games. Our main results are two-fold: (1) We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium (SEFCE), which runs in time polynomial in the size of the game, as well as the number of bits required to encode each input number. (2) We give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium (EFCE) up to machine precision, i.e., the algorithm achieves approximation error $\varepsilon$ in time polynomial in the size of the game, as well as $\log(1 / \varepsilon)$. Our algorithm for SEFCE is the first polynomial-time algorithm for equilibrium computation with commitment in such a general class of stochastic games. Existing algorithms for SEFCE typically make stronger assumptions such as no chance moves, and are designed for extensive-form games in the less succinct tree form. Our algorithm for approximately optimal EFCE is, to our knowledge, the first algorithm that achieves 3 desiderata simultaneously: approximate optimality, polylogarithmic dependency on the approximation error, and compatibility with stochastic games in the more succinct graph form. Existing algorithms achieve at most 2 of these desiderata, often also relying on additional technical assumptions.