---
_id: '4558'
abstract:
- lang: eng
text: We study perfect-information stochastic parity games. These are two-player
nonterminating games which are played on a graph with turn-based probabilistic
transitions. A play results in an infinite path and the conflicting goals of the
two players are ω-regular path properties, formalized as parity winning conditions.
The qualitative solution of such a game amounts to computing the set of vertices
from which a player has a strategy to win with probability 1 (or with positive
probability). The quantitative solution amounts to computing the value of the
game in every vertex, i.e., the highest probability with which a player can guarantee
satisfaction of his own objective in a play that starts from the vertex.For the
important special case of one-player stochastic parity games (parity Markov decision
processes) we give polynomial-time algorithms both for the qualitative and the
quantitative solution. The running time of the qualitative solution is O(d · m3/2)
for graphs with m edges and d priorities. The quantitative solution is based on
a linear-programming formulation.For the two-player case, we establish the existence
of optimal pure memoryless strategies. This has several important ramifications.
First, it implies that the values of the games are rational. This is in contrast
to the concurrent stochastic parity games of de Alfaro et al.; there, values are
in general algebraic numbers, optimal strategies do not exist, and ε-optimal strategies
have to be mixed and with infinite memory. Second, the existence of optimal pure
memoryless strategies together with the polynomial-time solution forone-player
case implies that the quantitative two-player stochastic parity game problem is
in NP ∩ co-NP. This generalizes a result of Condon for stochastic games with reachability
objectives. It also constitutes an exponential improvement over the best previous
algorithm, which is based on a doubly exponential procedure of de Alfaro and Majumdar
for concurrent stochastic parity games and provides only ε-approximations of the
values.
author:
- first_name: Krishnendu
full_name: Krishnendu Chatterjee
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Marcin
full_name: Jurdziński, Marcin
last_name: Jurdziński
- first_name: Thomas A
full_name: Thomas Henzinger
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Chatterjee K, Jurdziński M, Henzinger TA. Quantitative stochastic parity games.
In: SIAM; 2004:121-130.'
apa: 'Chatterjee, K., Jurdziński, M., & Henzinger, T. A. (2004). Quantitative
stochastic parity games (pp. 121–130). Presented at the SODA: Symposium on Discrete
Algorithms, SIAM.'
chicago: Chatterjee, Krishnendu, Marcin Jurdziński, and Thomas A Henzinger. “Quantitative
Stochastic Parity Games,” 121–30. SIAM, 2004.
ieee: 'K. Chatterjee, M. Jurdziński, and T. A. Henzinger, “Quantitative stochastic
parity games,” presented at the SODA: Symposium on Discrete Algorithms, 2004,
pp. 121–130.'
ista: 'Chatterjee K, Jurdziński M, Henzinger TA. 2004. Quantitative stochastic parity
games. SODA: Symposium on Discrete Algorithms, 121–130.'
mla: Chatterjee, Krishnendu, et al. *Quantitative Stochastic Parity Games*.
SIAM, 2004, pp. 121–30.
short: K. Chatterjee, M. Jurdziński, T.A. Henzinger, in:, SIAM, 2004, pp. 121–130.
conference:
name: 'SODA: Symposium on Discrete Algorithms'
date_created: 2018-12-11T12:09:28Z
date_published: 2004-01-01T00:00:00Z
date_updated: 2021-01-12T07:59:41Z
day: '01'
extern: 1
month: '01'
page: 121 - 130
publication_status: published
publisher: SIAM
publist_id: '153'
quality_controlled: 0
status: public
title: Quantitative stochastic parity games
type: conference
year: '2004'
...