Abstract: 
We consider twoplayer zerosum 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) onesided partialobservation (one player has partialobservation and the other player has completeobservation); and (c) completeobservation (both players have complete view of the game). The onesided partialobservation games have two important subclasses: the oneplayer games, known as partialobservation Markov decision processes (POMDPs), and the blind oneplayer 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 surewinning (i.e., all outcomes of a strategy have to satisfy the winning condition), almostsure winning (i.e., winning with probability 1), limitsure winning (i.e., winning with probability arbitrarily close to 1), and valuethreshold winning (i.e., winning with probability at least ν, where ν is a given rational).

Notes: 
The research was supported by Austrian Science Fund (FWF) Grant No. P 23499N23 on Modern Graph Algorithmic Techniques in Formal Verification, FWF NFN Grant No. S11407N23(RiSE), ERC Start grant (279307: Graph Games), Microsoft faculty fellows award, ERC Advanced grant QUAREM, and FWF Grant No. S11403N23 (RiSE).
