Kiefer, Stefan, Mayr, Richard, Shirmohammadi, Mahsa and Wojtczak, Dominik
(2017)
On Strong Determinacy of Countable Stochastic Games.
In: 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017-6-20 - 2017-6-23, Reykjavik, Iceland.
Text
main.pdf - Author Accepted Manuscript Download (366kB) |
Abstract
We study 2-player turn-based perfect-information stochastic games with countably infinite state space. The players aim at maximizing/minimizing the probability of a given event (i.e., measurable set of infinite plays), such as reachability, Büchi, ω-regular or more general objectives. These games are known to be weakly determined, i.e., they have value. However, strong determinacy of threshold objectives (given by an event ε and a threshold c ∈ [0,1]) was open in many cases: is it always the case that the maximizer or the minimizer has a winning strategy, i.e., one that enforces, against all strategies of the other player, that ε is satisfied with probability ≥ c (resp. <; c)? We show that almost-sure objectives (where c = 1) are strongly determined. This vastly generalizes a previous result on finite games with almost-sure tail objectives. On the other hand we show that ≥ 1/2 (co-)Biichi objectives are not strongly determined, not even if the game is finitely branching. Moreover, for almost-sure reachability and almost-sure Biichi objectives in finitely branching games, we strengthen strong determinacy by showing that one of the players must have a memory less deterministic (MD) winning strategy.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Additional Information: | INSPEC Accession Number: 17085187 |
Uncontrolled Keywords: | stochastic games, strong determinacy, infinite state space, Memory management, Games, game theory, minimisation, reachability analysis, stochastic processes, countable stochastic games, perfect-information stochastic games, reachability, general objectives, Biichi objectives |
Depositing User: | Symplectic Admin |
Date Deposited: | 31 May 2017 09:26 |
Last Modified: | 09 Sep 2024 13:08 |
DOI: | 10.1109/LICS.2017.8005134 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3007710 |