---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Krishnendu Chatterjee
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Thomas Henzinger
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
bibo_doi: 10.1007/11817949_25
bibo_volume: 4137
dct_date: 2006^xs_gYear
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Strategy improvement for stochastic Rabin and Streett games@
...