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.
[IST-2013-128-v1+1]
Download (228Kb)

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) 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 http://dx.doi.org/10.1007/978-3-642-54830-7_14
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: 21 Sep 2017 23:14
URI: https://repository.ist.ac.at/id/eprint/128

Actions (login required)

View Item View Item