Working Seminar on Formal Models, Discrete Structures, and Algorithms

Playing Stochastic Games Precisely

Vojtěch Forejt (University of Oxford)

When: April 30, 12:30pm

Where: room G2.91b/G215


I will present stochastic two-player games where the goal of one player is to achieve precisely a given expected value of the objective function, while the goal of the opponent is the opposite. The considered objectives include reachability, $\omega$-regular, discounted reward, and total reward.

I will show that precise value games are not determined, and compare the memory requirements for winning strategies.

For a large class of the games I will establish necessary and sufficient conditions for the existence of a winning strategy of the controller, as well as provide the constructions of compact strategies for the studied objectives.

The presented work was published at CONCUR 2012 and it is a joint paper with T. Chen, M. Kwiatkowska, A. Simaitis, A. Trivedi and M. Ummels.

If time permits, at the end I will talk about more recent work on multi-objective stochastic games, which is now under submission.