Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426787 | Information and Computation | 2013 | 25 Pages |
Abstract
We study continuous-time stochastic games with time-bounded reachability objectives and time-abstract strategies. We show that each vertex in such a game has a value (i.e., an equilibrium probability), and we classify the conditions under which optimal strategies exist. Further, we show how to compute ε-optimal strategies in finite games and provide detailed complexity estimations. Moreover, we show how to compute ε-optimal strategies in infinite games with finite branching and bounded rates where the bound as well as the successors of a given state are effectively computable. Finally, we show how to compute optimal strategies in finite uniform games.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Tomáš Brázdil, Vojtěch Forejt, Jan Krčál, Jan Křetínský, Antonín Kučera,