Determinacy and Optimal Strategies in Infinite-state Stochastic Reachability Games

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F13%3A00080195" target="_blank" >RIV/00216224:14330/13:00080195 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S030439751200967X" target="_blank" >http://www.sciencedirect.com/science/article/pii/S030439751200967X</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2012.10.038" target="_blank" >10.1016/j.tcs.2012.10.038</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Determinacy and Optimal Strategies in Infinite-state Stochastic Reachability Games

Popis výsledku v původním jazyce

We consider perfect-information reachability stochastic games for 2 players on countable graphs. Such a game is strongly determined if, whenever we fix an inequality ~E{&gt;,&gt;=} and a threshold p, either Player Max has a strategy which forces the value of the game to satisfy ~p against any strategy of Player Min, or Min has a strategy which forces the opposite against any strategy of Max. One of our results shows that whenever one of the players has an optimal strategy in every state of a game, thenthis game is strongly determined. This significantly generalises, e.g., recent results on finitely-branching reachability games. For strong determinacy, our methods are substantially different, based on which player has the optimal strategy, because theroles of the players are not symmetric. We also do not restrict the branching of the games, and where we provide an extension of results for finitely-branching games, we had to overcome significant complications and employ new methods as

Název v anglickém jazyce

Determinacy and Optimal Strategies in Infinite-state Stochastic Reachability Games

Popis výsledku anglicky

We consider perfect-information reachability stochastic games for 2 players on countable graphs. Such a game is strongly determined if, whenever we fix an inequality ~E{&gt;,&gt;=} and a threshold p, either Player Max has a strategy which forces the value of the game to satisfy ~p against any strategy of Player Min, or Min has a strategy which forces the opposite against any strategy of Max. One of our results shows that whenever one of the players has an optimal strategy in every state of a game, thenthis game is strongly determined. This significantly generalises, e.g., recent results on finitely-branching reachability games. For strong determinacy, our methods are substantially different, based on which player has the optimal strategy, because theroles of the players are not symmetric. We also do not restrict the branching of the games, and where we provide an extension of results for finitely-branching games, we had to overcome significant complications and employ new methods as

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2013

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 periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

493

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

18

Strana od-do

80-97

Kód UT WoS článku

000321410000007

EID výsledku v databázi Scopus

—