Working Seminar on Formal Models, Discrete Structures, and Algorithms

Exact algorithms for solving stochastic games

Michal Koucký (Czech Academy of Sciences in Prague)

When: May 30, 2pm

Where: room G2.91b


Shapley's discounted stochastic games, Everett's recursive games and Gillette's undiscounted stochastic games are classical models of game theory describing two-player zero-sum games of potentially infinite duration. We describe algorithms for exactly solving these games. When the number of positions of the game is constant, our algorithms run in polynomial time and are the first algorithms with this property.

Joint work with Kristoffer Arnsfelt Hansen, Niels Lauritzen, Peter Bro Miltersen and Elias P. Tsigaridas.