A survey of stochastic games with limsup and liminf objectives

K. Chatterjee, L. Doyen, T.A. Henzinger, in:, Springer, 2009, pp. 1–15.

Download
OA 187.42 KB

Conference Paper | Published | English
Department
Series Title
LNCS
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.
Publishing Year
Date Published
2009-06-24
Acknowledgement
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.
Volume
5556
Page
1 - 15
Conference
ICALP: Automata, Languages and Programming
Conference Location
Rhodos, Greece
Conference Date
2009-07-05 – 2009-07-12
IST-REx-ID

Cite this

Chatterjee K, Doyen L, Henzinger TA. A survey of stochastic games with limsup and liminf objectives. In: Vol 5556. Springer; 2009:1-15. doi:10.1007/978-3-642-02930-1_1
Chatterjee, K., Doyen, L., & Henzinger, T. A. (2009). A survey of stochastic games with limsup and liminf objectives (Vol. 5556, pp. 1–15). Presented at the ICALP: Automata, Languages and Programming, Rhodos, Greece: Springer. https://doi.org/10.1007/978-3-642-02930-1_1
Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “A Survey of Stochastic Games with Limsup and Liminf Objectives,” 5556:1–15. Springer, 2009. https://doi.org/10.1007/978-3-642-02930-1_1.
K. Chatterjee, L. Doyen, and T. A. Henzinger, “A survey of stochastic games with limsup and liminf objectives,” presented at the ICALP: Automata, Languages and Programming, Rhodos, Greece, 2009, vol. 5556, pp. 1–15.
Chatterjee K, Doyen L, Henzinger TA. 2009. A survey of stochastic games with limsup and liminf objectives. ICALP: Automata, Languages and Programming, LNCS, vol. 5556. 1–15.
Chatterjee, Krishnendu, et al. A Survey of Stochastic Games with Limsup and Liminf Objectives. Vol. 5556, Springer, 2009, pp. 1–15, doi:10.1007/978-3-642-02930-1_1.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:13:11Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar