Personal tools
You are here: Home Events LFCS seminar: Richard Mayr: On strong determinacy of countable stochastic games

LFCS seminar: Richard Mayr: On strong determinacy of countable stochastic games

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
When May 23, 2017
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Add event to calendar vCal
iCal

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, Buchi, omega-regular or more general Borel 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 \in [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 the objective is satisfied with probability \ge 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 \ge 1/2 (co-)Buchi objectives are not strongly determined, not even if the game is finitely branching. Moreover, for almost-sure reachability and almost-sure Buchi objectives in finitely branching games, we strengthen strong determinacy by showing that one of the players must have a memoryless deterministic (MD) winning strategy.

References: On Strong Determinacy of Countable Stochastic Games. Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Dominik Wojtczak. To appear in LICS 2017. https://arxiv.org/abs/1704.05003

Document Actions