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

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: | 23 Apr 2018 05:57 |

URI: | https://repository.ist.ac.at/id/eprint/128 |

### Actions (login required)

View Item |