Perfect-information stochastic mean-payoff parity games
LNCS
Chatterjee, Krishnendu
Doyen, Laurent
Gimbert, Hugo
Oualhadj, Youssouf
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).
Springer
2014
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://research-explorer.app.ist.ac.at/record/2212
Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. Perfect-information stochastic mean-payoff parity games. In: Vol 8412. Springer; 2014:210-225. doi:<a href="https://doi.org/10.1007/978-3-642-54830-7_14">10.1007/978-3-642-54830-7_14</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-54830-7_14
info:eu-repo/grantAgreement/FWF/P 23499-N23
info:eu-repo/grantAgreement/FWF/S11407
info:eu-repo/grantAgreement/EC/FP7/279307
info:eu-repo/semantics/closedAccess