A survey of partial-observation stochastic parity games

K. Chatterjee, L. Doyen, T.A. Henzinger, Formal Methods in System Design 43 (2012) 268–284.

Download
OA 163.98 KB

Journal Article | Published | English
Abstract
We consider two-player zero-sum stochastic games on graphs with ω-regular winning conditions specified as parity objectives. These games have applications in the design and control of reactive systems. We survey the complexity results for the problem of deciding the winner in such games, and in classes of interest obtained as special cases, based on the information and the power of randomization available to the players, on the class of objectives and on the winning mode. On the basis of information, these games can be classified as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) complete-observation (both players have complete view of the game). The one-sided partial-observation games have two important subclasses: the one-player games, known as partial-observation Markov decision processes (POMDPs), and the blind one-player games, known as probabilistic automata. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Finally, various classes of games are obtained by restricting the parity objective to a reachability, safety, Büchi, or coBüchi condition. We also consider several winning modes, such as sure-winning (i.e., all outcomes of a strategy have to satisfy the winning condition), almost-sure winning (i.e., winning with probability 1), limit-sure winning (i.e., winning with probability arbitrarily close to 1), and value-threshold winning (i.e., winning with probability at least ν, where ν is a given rational).
Publishing Year
Date Published
2012-10-01
Journal Title
Formal Methods in System Design
Acknowledgement
The research was supported by Austrian Science Fund (FWF) Grant No. P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, FWF NFN Grant No. S11407-N23(RiSE), ERC Start grant (279307: Graph Games), Microsoft faculty fellows award, ERC Advanced grant QUAREM, and FWF Grant No. S11403-N23 (RiSE).
Volume
43
Issue
2
Page
268 - 284
IST-REx-ID

Cite this

Chatterjee K, Doyen L, Henzinger TA. A survey of partial-observation stochastic parity games. Formal Methods in System Design. 2012;43(2):268-284. doi:10.1007/s10703-012-0164-2
Chatterjee, K., Doyen, L., & Henzinger, T. A. (2012). A survey of partial-observation stochastic parity games. Formal Methods in System Design, 43(2), 268–284. https://doi.org/10.1007/s10703-012-0164-2
Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “A Survey of Partial-Observation Stochastic Parity Games.” Formal Methods in System Design 43, no. 2 (2012): 268–84. https://doi.org/10.1007/s10703-012-0164-2.
K. Chatterjee, L. Doyen, and T. A. Henzinger, “A survey of partial-observation stochastic parity games,” Formal Methods in System Design, vol. 43, no. 2, pp. 268–284, 2012.
Chatterjee K, Doyen L, Henzinger TA. 2012. A survey of partial-observation stochastic parity games. Formal Methods in System Design. 43(2), 268–284.
Chatterjee, Krishnendu, et al. “A Survey of Partial-Observation Stochastic Parity Games.” Formal Methods in System Design, vol. 43, no. 2, Springer, 2012, pp. 268–84, doi:10.1007/s10703-012-0164-2.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:11:27Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar