BROŽEK, Václav. Determinacy and Optimal Strategies in Infinite-state Stochastic Reachability Games. Theoretical Computer Science. Amsterdam: Elsevier, 2013, roč. 493, č. 1, s. 80-97. ISSN 0304-3975. doi:10.1016/j.tcs.2012.10.038.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Determinacy and Optimal Strategies in Infinite-state Stochastic Reachability Games
Autoři BROŽEK, Václav (203 Česká republika, garant, domácí).
Vydání Theoretical Computer Science, Amsterdam, Elsevier, 2013, 0304-3975.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Nizozemsko
Utajení není předmětem státního či obchodního tajemství
WWW URL
Impakt faktor Impact factor: 0.516
Kód RIV RIV/00216224:14330/13:00080195
Organizační jednotka Fakulta informatiky
Doi http://dx.doi.org/10.1016/j.tcs.2012.10.038
UT WoS 000321410000007
Klíčová slova anglicky Stochastic games; Reachability; Determinacy; Optimal strategies
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 22. 5. 2015 06:16.
Anotace
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{>,>=} 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, then this 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 the roles 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 well. The other result is finding a subclass of stochastic games where Player Max has an optimal strategy in each state. The subclass is defined by the property that if v is an accumulation point of the set of all values of a game then v=0. These results complement recent results classifying the existence of an optimal strategy for Player Min, and our general strong-determinacy theorem applies here as well. We also apply our results for Max in the context of recently studied One-Counter stochastic games. This work extends a workshop version of this paper which appeared in GandALF 2011, in particular, we prove a conjecture raised in that paper for the class of all reachability games.
VytisknoutZobrazeno: 28. 6. 2022 11:08