Author(s):

Chatterjee, Krishnendu; Doyen, Laurent; Gimbert, Hugo; Oualhadj, Youssouf

Title: 
Perfectinformation stochastic meanpayoff 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/2player 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/2player 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 meanpayoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the meanpayoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2player games (where all transitions are deterministic). We present an algorithm running in time O(d·n2d·MeanGame) to compute the set of almostsure 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 almostsure winning states in 2 1/2player meanpayoff 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 513, 2014

Conference Location:

Grenoble, France

Publisher:

Springer

Date Published:

20140401

Start Page: 
210

End Page:

225

Sponsor: 
This research was supported by Austrian Science Fund (FWF) Grant No P23499 N23, FWF NFN Grant No S11407N23 (RiSE), ERC Start grant (279307: Graph Games), Microsoft Faculty Fellowship Award, and European project Cassting (FP7601148).

DOI: 
10.1007/9783642548307_14

Notes: 
A Technical Report of this paper is available at:
https://repository.ist.ac.at/id/eprint/128.

Open access: 
yes (repository) 