---
_id: '6889'
abstract:
- lang: eng
  text: '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. '
alternative_title:
- LIPIcs
article_number: '6'
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Nir
  full_name: Piterman, Nir
  last_name: Piterman
citation:
  ama: 'Chatterjee K, Piterman N. Combinations of Qualitative Winning for Stochastic
    Parity Games. In: Vol 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2019. doi:<a href="https://doi.org/10.4230/LIPICS.CONCUR.2019.6">10.4230/LIPICS.CONCUR.2019.6</a>'
  apa: 'Chatterjee, K., &#38; Piterman, N. (2019). Combinations of Qualitative Winning
    for Stochastic Parity Games (Vol. 140). Presented at the CONCUR: Conference on
    Concurrency Theory, Amsterdam, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPICS.CONCUR.2019.6">https://doi.org/10.4230/LIPICS.CONCUR.2019.6</a>'
  chicago: Chatterjee, Krishnendu, and Nir Piterman. “Combinations of Qualitative
    Winning for Stochastic Parity Games,” Vol. 140. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2019. <a href="https://doi.org/10.4230/LIPICS.CONCUR.2019.6">https://doi.org/10.4230/LIPICS.CONCUR.2019.6</a>.
  ieee: 'K. Chatterjee and N. Piterman, “Combinations of Qualitative Winning for Stochastic
    Parity Games,” presented at the CONCUR: Conference on Concurrency Theory, Amsterdam,
    Netherlands, 2019, vol. 140.'
  ista: 'Chatterjee K, Piterman N. 2019. Combinations of Qualitative Winning for Stochastic
    Parity Games. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 140, 6.'
  mla: Chatterjee, Krishnendu, and Nir Piterman. <i>Combinations of Qualitative Winning
    for Stochastic Parity Games</i>. Vol. 140, 6, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2019, doi:<a href="https://doi.org/10.4230/LIPICS.CONCUR.2019.6">10.4230/LIPICS.CONCUR.2019.6</a>.
  short: K. Chatterjee, N. Piterman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2019.
conference:
  end_date: 2019-08-30
  location: Amsterdam, Netherlands
  name: 'CONCUR: Conference on Concurrency Theory'
  start_date: 2019-08-27
date_created: 2019-09-18T08:11:43Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2025-07-10T11:53:59Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPICS.CONCUR.2019.6
file:
- access_level: open_access
  checksum: 7b2ecfd4d9d02360308c0ca986fc10a7
  content_type: application/pdf
  creator: kschuh
  date_created: 2019-10-01T08:49:45Z
  date_updated: 2020-07-14T12:47:43Z
  file_id: '6923'
  file_name: 2019_LIPIcs_Chatterjee.pdf
  file_size: 509163
  relation: main_file
file_date_updated: 2020-07-14T12:47:43Z
has_accepted_license: '1'
intvolume: '       140'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Combinations of Qualitative Winning for Stochastic Parity Games
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 140
year: '2019'
...