Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Special Session Talk:
Solving Simple Stochastic Games

Edit abstract data

Speaker: Hugo Gimbert
Author(s): Hugo Gimbert, Florian Horn


A Simple Stochastic Game is played by two players called Min and Max, moving
turn by turn a pebble along edges of a graph.
Player Max wants the pebble to reach a special vertex called the target vertex.
On some special vertices called random vertices, the next vertex is chosen
randomly according to some fixed transition probabilities.

Solving a simple stochastic game consists in computing the maximal probability
with which player Max can enforce the pebble to reach the target vertex.

In this talk, we will survey existing algorithms for solving Simple Stochastic
Games, and present a new algorithm which is especially efficient for games with
few random vertices.

websites: Arnold Beckmann 2007-12-23 Valid HTML 4.01! Valid CSS!