Playing Stochastic Games Precisely

Taloue ChenTaloue Chen, Vojtech ForejtVojtech Forejt, Marta KwiatkowskaMarta Kwiatkowska, Aistis SimaitisAistis Simaitis, Ashutosh TrivediAshutosh Trivedi, Michael UmmelsMichael Ummels

DOI Link

Taloue Chen, Vojtech Forejt, Marta Kwiatkowska, Aistis Simaitis, Ashutosh Trivedi, Michael Ummels
Playing Stochastic Games Precisely
Proc. of the 23rd International Conference on Concurrency Theory (CONCUR), volume 7454 of Lecture Notes in Computer Science, 348--363, 2012. Springer

Details
Bibtex

KurzfassungAbstract
We study 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. Potential applications for such games include controller synthesis problems where the optimisation objective is to maximise or minimise a given payoff function while respecting a strict upper or lower bound, respectively. We consider a number of objective functions including reachability, ω-regular, discounted reward, and total reward. We show that precise value games are not determined, and compare the memory requirements for winning strategies. For stopping games we establish necessary and sufficient conditions for the existence of a winning strategy of the controller for a large class of functions, as well as provide the constructions of compact strategies for the studied objectives.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-32940-1_25.

@inproceedings{CFKSTU2012,
  author    = {Taloue Chen and Vojtech Forejt and Marta Kwiatkowska and Aistis
               Simaitis and Ashutosh Trivedi and Michael Ummels},
  title     = {Playing Stochastic Games Precisely},
  booktitle = {Proc. of the 23rd International Conference on Concurrency Theory
               (CONCUR)},
  series    = {Lecture Notes in Computer Science},
  volume    = {7454},
  publisher = {Springer},
  year      = {2012},
  pages     = {348--363},
  doi       = {10.1007/978-3-642-32940-1_25}
}