Kurt Gödel Research Center

2013 seminar talk: Simple stochastic games: a state of the art

Talk held by Yann Strozecki (Versailles University, France) at the KGRC seminar on 2013-06-06.

Abstract

In this talk I present simple stochastic games and some related games as parity or discounted payoff games. They can be used to solve interesting problems, such as the model checking of the mu calculus. Moreover, these games generalize Markov decision processes, repeated games, and linear programming which is perhaps the most ubiquituous technique in computer science.

The main problem is to compute optimal strategies for the two players, which seems to be hard because of the randomness and because a play can be infinite. It turns out that the problem is computable and even in NP thanks to general ideas from game theory. However all algorithms proposed are exponential. I will review the fundamental results on these games: existence of a unique pure and positional optimal strategy, its caracterisation, the fixed point formulation ... I will also sketch some of the best algorithms, which are all very simple to describe but often hard to analyze.