| |
| Algorithms for Solving Stochastic Games |
Marcin Jurdzin'ski
(Univ. of Warwick, UK)
|
| Duration: 180 minutes |
ABSTRACT:
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.
| |