Computing Equilibria in Multiplayer Stochastic Games of Imperfect Information

Computing a Nash equilibrium in multiplayer stochastic games is a notoriously difficult problem. Prior algorithms have been proven to converge in extremely limited settings and have only been tested on small problems. In contrast, we recently presented an algorithm for computing approximate jam/fold equilibrium strategies in a three-player no-limit Texas hold'em tournament — a very large real-world stochastic game of imperfect information. In this paper we show that it is possible for that algorithm to converge to a non-equilibrium strategy profile. However, we develop an ex post procedure that determines exactly how much each player can gain by deviating from his strategy, and confirm that the strategies computed in that earlier paper actually do constitute an epsilon-equilibrium for a very small epsilon (0.5% of the tournament entry fee). Next, we develop several new algorithms for computing a Nash equilibrium in multiplayer stochastic games (with perfect or imperfect information) which can provably never converge to a non-equilibrium. Experiments show that one of these algorithms outperforms the original algorithm on the same poker tournament. In short, we present the first algorithms for provably computing an epsilon-equilibrium of a large stochastic game for small epsilon. Finally, we present an efficient algorithm that minimizes external regret in both the perfect and imperfect information case.

Sam Ganzfried, Tuomas Sandholm