Playing Stochastic Games Precisely

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F12%3A00064715" target="_blank" >RIV/00216224:14330/12:00064715 - isvavai.cz</a>

Výsledek na webu

<a href="http://qav.comlab.ox.ac.uk/papers/concur12precise.pdf" target="_blank" >http://qav.comlab.ox.ac.uk/papers/concur12precise.pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-32940-1_25" target="_blank" >10.1007/978-3-642-32940-1_25</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Playing Stochastic Games Precisely

Popis výsledku v původním jazyce

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 synthesisproblems 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.

Název v anglickém jazyce

Playing Stochastic Games Precisely

Popis výsledku anglicky

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 synthesisproblems 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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/LA09016" target="_blank" >LA09016: Účast ČR v European Research Consortium for Informatics and Mathematics (ERCIM)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

CONCUR 2012 - Concurrency Theory - 23rd International Conference

ISBN

9783642329395

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

15

Strana od-do

348-363

Název nakladatele

Springer

Místo vydání

Berlin, Heidelberg

Místo konání akce

Newcastle

Datum konání akce

1. 1. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—