Strategy improvement for stochastic Rabin and Streett games

K. Chatterjee, T.A. Henzinger, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2006, pp. 375–389.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Series Title
LNCS
Abstract
A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with omega-regular winning conditions specified as Rabin or Streett objectives. These games are NP-complete and coNP-complete, respectively. The value of the game for a player at a state s given an objective Phi is the maximal probability with which the player can guarantee the satisfaction of Phi from s. We present a strategy-improvement algorithm to compute values in stochastic Rabin games, where an improvement step involves solving Markov decision processes (MDPs) and nonstochastic Rabin games. The algorithm also computes values for stochastic Streett games but does not directly yield an optimal strategy for Streett objectives. We then show how to obtain an optimal strategy for Streett objectives by solving certain nonstochastic Streett games.
Publishing Year
Date Published
2006-08-10
Acknowledgement
This research was supported in part by the NSF grants CCR-0225610 and CCR-0234690, and by the SNSF under the Indo-Swiss Joint Research Programme.
Volume
4137
Page
375 - 389
Conference
CONCUR: Concurrency Theory
IST-REx-ID

Cite this

Chatterjee K, Henzinger TA. Strategy improvement for stochastic Rabin and Streett games. In: Vol 4137. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2006:375-389. doi:10.1007/11817949_25
Chatterjee, K., & Henzinger, T. A. (2006). Strategy improvement for stochastic Rabin and Streett games (Vol. 4137, pp. 375–389). Presented at the CONCUR: Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/11817949_25
Chatterjee, Krishnendu, and Thomas A Henzinger. “Strategy Improvement for Stochastic Rabin and Streett Games,” 4137:375–89. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2006. https://doi.org/10.1007/11817949_25.
K. Chatterjee and T. A. Henzinger, “Strategy improvement for stochastic Rabin and Streett games,” presented at the CONCUR: Concurrency Theory, 2006, vol. 4137, pp. 375–389.
Chatterjee K, Henzinger TA. 2006. Strategy improvement for stochastic Rabin and Streett games. CONCUR: Concurrency Theory, LNCS, vol. 4137. 375–389.
Chatterjee, Krishnendu, and Thomas A. Henzinger. Strategy Improvement for Stochastic Rabin and Streett Games. Vol. 4137, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2006, pp. 375–89, doi:10.1007/11817949_25.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar