Playing Stochastic Games Precisely

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

CHEN Taolue FOREJT Vojtěch KWIATKOWSKA Marta SIMAITIS Aistis TRIVEDI Ashutosh UMMELS Michael

Rok publikování 2012
Druh Článek ve sborníku
Konference CONCUR 2012 - Concurrency Theory - 23rd International Conference
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://qav.comlab.ox.ac.uk/papers/concur12precise.pdf
Doi http://dx.doi.org/10.1007/978-3-642-32940-1_25
Obor Informatika
Klíčová slova Stochastic games; Reachability
Popis 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, omega-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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.