---
_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'
...