--- _id: '3888' abstract: - lang: eng text: 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. 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. alternative_title: - LNCS author: - first_name: Krishnendu full_name: Krishnendu Chatterjee id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Thomas A full_name: Thomas Henzinger id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 citation: ama: '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' apa: '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' chicago: 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. ieee: '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.' ista: 'Chatterjee K, Henzinger TA. 2006. Strategy improvement for stochastic Rabin and Streett games. CONCUR: Concurrency Theory, LNCS, vol. 4137, 375–389.' mla: 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. short: K. Chatterjee, T.A. Henzinger, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2006, pp. 375–389. conference: name: 'CONCUR: Concurrency Theory' date_created: 2018-12-11T12:05:43Z date_published: 2006-08-10T00:00:00Z date_updated: 2021-01-12T07:52:58Z day: '10' doi: 10.1007/11817949_25 extern: 1 intvolume: ' 4137' month: '08' page: 375 - 389 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '2278' quality_controlled: 0 status: public title: Strategy improvement for stochastic Rabin and Streett games type: conference volume: 4137 year: '2006' ...