Tutorial T1
Algorithms for Solving Stochastic Games
Marcin Jurdzin'ski
(Univ. of Warwick, UK)
Duration: 180 minutes
Stochastic games are repeated games with probabilistic transitions and with payoffs that are functions of the whole play, i.e., the history of the players' interaction. The theory of stochastic games is surveyed as a basis for formal specification and algorithmic analysis of quantitative properties of systems. A general framework of games with Borel measurable payoff functions is presented, as well as important special cases of discounted, limiting average, and omega-regular payoffs. Algorithmic methods for solving stochastic games are surveyed, including value iteration, strategy improvement, mathematical programming, and graph theoretic algorithms. Important subclasses of the general stochastic game model are discussed, including Markov decision processes, perfect-information games, and non-stochastic 2-player games.
Web Maintenance Person.