When: April 30, 12:30pm
Where: room G2.91b/G215
Abstract
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.