A Survey of Stochastic Games with Limsup and Liminf Objectives

Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger

A stochastic game is a two-player game played on a graph, where in each state the successor is chosen either by one of the players, or according to a probability distribution. We survey stochastic games with limsup and liminf objectives. A real-valued reward is assigned to each state, and the value of an infinite path is the limsup (resp. liminf) of all rewards along the path. The value of a stochastic game is the maximal expected value of an infinite path that can be achieved by resolving the decisions of the first player. We present the complexity of computing values of stochastic games and their subclasses, and the complexity of optimal strategies in such games.

Proceedings of the 36th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science 5556, Part II, Springer, 2009, pp. 1-15.

Download inofficial, sometimes updated PostScript / PDF document. © 2009 Springer.