---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Krishnendu Chatterjee
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Marcin
foaf_name: Jurdziński, Marcin
foaf_surname: Jurdziński
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Thomas Henzinger
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
dct_date: 2004^xs_gYear
dct_publisher: SIAM@
dct_title: Quantitative stochastic parity games@
...