On Strong Determinacy of Countable Stochastic Games

Richard Mayr, Stefan Kiefer, Mahsa Shirmohammadi, Dominik Wojtczak

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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\"uchi, omega-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 the objective 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-)B\"uchi objectives are not strongly determined, not even if the game is finitely branching. Moreover, for almost-sure reachability and almost-sure B\"uchi objectives in finitely branching games, we strengthen strong determinacy by showing that one of the players must have a memoryless deterministic (MD) winning strategy.
Original languageEnglish
Title of host publication2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages13
ISBN (Electronic)978-1-5090-3018-7
DOIs
Publication statusPublished - 18 Aug 2017
Event2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science - Reykjavik, Reykjavik, Iceland
Duration: 20 Jun 201723 Jun 2017
http://lics.siglog.org/lics17/

Conference

Conference2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science
Abbreviated titleLICS 2017
Country/TerritoryIceland
CityReykjavik
Period20/06/1723/06/17
Internet address

Keywords / Materials (for Non-textual outputs)

  • stochastic games, strong determinacy, infinite state space

Fingerprint

Dive into the research topics of 'On Strong Determinacy of Countable Stochastic Games'. Together they form a unique fingerprint.

Cite this