| Summary: | <p>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.</p> <br/> <p>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)?</p> <br/> <p>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-)Büchi objectives are not strongly determined, not even if the game is finitely branching.</p> <br/> <p>Moreover, for almost-sure reachability and almost-sure Büchi objectives in finitely branching games, we strengthen strong determinacy by showing that one of the players must have a memoryless deterministic (MD) winning strategy.</p>
|
|---|