University of Leicester
Browse

Combinations of Qualitative Winning for Stochastic Parity Games

Download (497.23 kB)
Version 2 2020-04-29, 09:42
Version 1 2020-04-29, 09:40
conference contribution
posted on 2020-04-29, 09:42 authored by N Piterman, K Chatterjee
We study Markov decision processes and turn-based stochastic games with parity conditions. There are three qualitative winning criteria, namely, sure winning, which requires all paths to satisfy the condition, almost-sure winning, which requires the condition to be satisfied with probability 1, and limit-sure winning, which requires the condition to be satisfied with probability arbitrarily close to 1. We study the combination of two of these criteria for parity conditions, e.g., there are two parity conditions one of which must be won surely, and the other almost-surely. The problem has been studied recently by Berthon et al. for MDPs with combination of sure and almost-sure winning, under infinite-memory strategies, and the problem has been established to be in NP cap co-NP. Even in MDPs there is a difference between finite-memory and infinite-memory strategies. Our main results for combination of sure and almost-sure winning are as follows: (a) we show that for MDPs with finite-memory strategies the problem is in NP cap co-NP; (b) we show that for turn-based stochastic games the problem is co-NP-complete, both for finite-memory and infinite-memory strategies; and (c) we present algorithmic results for the finite-memory case, both for MDPs and turn-based stochastic games, by reduction to non-stochastic parity games. In addition we show that all the above complexity results also carry over to combination of sure and limit-sure winning, and results for all other combinations can be derived from existing results in the literature. Thus we present a complete picture for the study of combinations of two qualitative winning criteria for parity conditions in MDPs and turn-based stochastic games.

Funding

Krishnendu Chatterjee: This research is funded by Austrian Science Fund (FWF) NFN Grant S11407-N23 (RiSE/SHiNE), and Vienna Science and Technology Fund (WWTF) Project ICT15-003. Nir Piterman: This research is funded by the ERC consolidator grant D-SynMA under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 772459).

History

Citation

Leibniz International Proceedings in Informatics Article No. 6; pp. 6:1–6:17 30th International Conference on Concurrency Theory (CONCUR 2019).

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Informatics

Source

30th International Conference on Concurrency Theory (Concur 2019)

Version

  • VoR (Version of Record)

Published in

Leibniz International Proceedings in Informatics (LIPIcs)

Volume

140

Pagination

6:1–6:17

Publisher

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

eissn

1868-8969

Acceptance date

2019-06-25

Copyright date

2019

Publisher version

https://drops.dagstuhl.de/opus/volltexte/2019/10908/

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC