The patience of concurrent stochastic games with safety and reachability objectives

K. Chatterjee, R. Ibsen-Jensen, K. Hansen, The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives, IST Austria, 2015.

Download
OA 661.01 KB

Technical Report | Published | English
Department
Series Title
IST Austria Technical Report
Abstract
We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. We consider reachability objectives that given a target set of states require that some state in the target set is visited, and the dual safety objectives that given a target set require that only states in the target set are visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed. Our main results are as follows: We show that in two-player zero-sum concurrent stochastic games (with reachability objective for one player and the complementary safety objective for the other player): (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. In general we study the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that if there is at least one player with reachability objective, then doubly-exponential patience is needed in general for epsilon-Nash equilibrium strategies, whereas in contrast if all players have safety objectives, then the optimal bound on patience for epsilon-Nash equilibrium strategies is only exponential.
Publishing Year
Date Published
2015-02-19
Page
25
ISSN
IST-REx-ID

Cite this

Chatterjee K, Ibsen-Jensen R, Hansen K. The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives. IST Austria; 2015. doi:10.15479/AT:IST-2015-322-v1-1
Chatterjee, K., Ibsen-Jensen, R., & Hansen, K. (2015). The patience of concurrent stochastic games with safety and reachability objectives. IST Austria. https://doi.org/10.15479/AT:IST-2015-322-v1-1
Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Kristoffer Hansen. The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-322-v1-1.
K. Chatterjee, R. Ibsen-Jensen, and K. Hansen, The patience of concurrent stochastic games with safety and reachability objectives. IST Austria, 2015.
Chatterjee K, Ibsen-Jensen R, Hansen K. 2015. The patience of concurrent stochastic games with safety and reachability objectives, IST Austria, 25p.
Chatterjee, Krishnendu, et al. The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives. IST Austria, 2015, doi:10.15479/AT:IST-2015-322-v1-1.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T11:53:31Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar