Perfect-information stochastic mean-payoff parity games Conference Paper


Author(s): Chatterjee, Krishnendu; Doyen, Laurent; Gimbert, Hugo; Oualhadj, Youssouf
Title: Perfect-information stochastic mean-payoff parity games
Title Series: LNCS
Affiliation IST Austria
Abstract: The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2 1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2 1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic). We present an algorithm running in time O(d·n2d·MeanGame) to compute the set of almost-sure winning states from which the objective can be ensured with probability 1, where n is the number of states of the game, d the number of priorities of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states in 2 1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective).
Conference Title: FoSSaCS: Foundations of Software Science and Computation Structures
Volume: 8412
Conference Dates: April 5-13, 2014
Conference Location: Grenoble, France
Publisher: Springer  
Date Published: 2014-04-01
Start Page: 210
End Page: 225
Sponsor: This research was supported by Austrian Science Fund (FWF) Grant No P23499- N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), Microsoft Faculty Fellowship Award, and European project Cassting (FP7-601148).
DOI: 10.1007/978-3-642-54830-7_14
Notes: A Technical Report of this paper is available at: https://repository.ist.ac.at/id/eprint/128.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work