Loading...
Please wait, while we are loading the content...
Similar Documents
A survey of partial-observation stochastic parity games.
| Content Provider | CiteSeerX |
|---|---|
| Author | Chatterjee, Krishnendu Doyen, Laurent Henzinger, Thomas A. |
| 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) partialobservation (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). |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Partial-observation Stochastic Parity Game Two-player Zero-sum Stochastic Game Important Subclass One-sided Partial-observation Game Probability Distribution Special Case Limit-sure Winning Actual Random Choice Various Class Parity Objective One-player Game Pure Strategy Winning Mode Complete View Partial View Chi Condition Complexity Result Partial-observation Markov Decision Process Action Invisible Blind One-player Game Almost-sure Winning Value-threshold Winning Reactive System Probabilistic Automaton Full Randomization One-sided Partial-observation |
| Content Type | Text |
