Algorithms for Solving Simple Stochastic Games

Prelegent(ci)

Hugo Gimbert (joint work with F. Horn)

Afiliacja

Uniwersytet Warszawski

Termin

10 października 2007 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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 vertexc 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 present several known algorithms for solving such games, as well as a new algorithm specially designed for games with few random vertices.

---