A survey of stochastic games with limsup and liminf objectives Conference Paper


Author(s): Chatterjee, Krishnendu; Doyen, Laurent; Henzinger, Thomas A
Title: A survey of stochastic games with limsup and liminf objectives
Title Series: LNCS
Affiliation IST Austria
Abstract: A stochastic game is a two-player game played oil 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 re-ward is assigned to each state, and the value of all 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 call he 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.
Conference Title: ICALP: Automata, Languages and Programming
Volume: 5556
Conference Dates: July 5-12, 2009
Conference Location: Rhodes, Greece
Publisher: Springer  
Location: Berlin, Heidelberg
Date Published: 2009-06-24
Start Page: 1
End Page: 15
URL:
DOI: 10.1007/978-3-642-02930-1_1
Notes: This research was supported in part by the Swiss National Science Foundation under the Indo-Swiss Joint Research Programme, by the European Network of Excellence on Embedded Systems Design (ArtistDesign), by the European projects COMBEST, Quasimodo, Gasics, by the PAI program Moves funded by the Belgian Federal Government, and by the CFV (Federated Center in Verification) funded by the F.R.S.-FNRS.
Open access: yes (repository)
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work