Laurent Doyen,
The Complexity of Partial-observation Stochastic Games

We consider two-player stochastic games played on graphs with omega-regular objectives. Graph games have many applications in computer science, such as in logics, model-checking, synthesis, refinement and compatibility checking. In many cases, turn-based games with perfect observation are considered and a rich theory has been developed. However, the hypothesis of perfect observation for both players is often not realistic in practice. For example, in a concurrent system where the players represent individual processes, each process has only access to the public variables of the other processes, not to their private variables. Such problems are better modeled in the more general framework of partial-observation games.

The study of partial-observation games is considerably more complicated than games of perfect observation. Several results and properties of perfect-observation omega-regular games break under partial observation, such as determinacy, existence of pure memoryless optimal strategies, and even decidability for general omega-regular objectives.

We present a survey of basic results in the theory of partial-observation games on graphs, about the structural complexity of winning strategies (randomization and memory requirements) and the algorithmic complexity of deciding the winner of the game. Then we present recent results and open problems for partial-observation stochastic games with reachability objectives, and establish surprising connections between some of these problems and classical problems for counter systems.