When: May 30, 2pm
Where: room G2.91b
Abstract
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.