Perfect-Information Stochastic Mean-Payoff Parity Games

Chatterjee, Krishnendu and Doyen, Laurent and Gimbert, Hugo and Oualhadj, Youssouf (2013) Perfect-Information Stochastic Mean-Payoff Parity Games. Technical Report. IST Austria.

[img] Text
full_stoch_mpp.pdf - Published Version
Available under License All rights reserved.
Download (228Kb)


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) with only parity objectives, or with only mean-payoff objectives. We present an algorithm running in time O(d · n^{2d}·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).

Item Type: Monograph (Technical Report)
Additional Information: A short version of this technical report is available at Springer via
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data
500 Science > 510 Mathematics
Research Group: Chatterjee Group
Depositing User: Prof Krishnendu Chatterjee
Date Deposited: 08 Jul 2013 08:23
Last Modified: 16 Jul 2019 22:51

Actions (login required)

View Item View Item