## 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.