Continuous-Time Stochastic Games with Time-Bounded Reachability

Investor logo

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BRÁZDIL Tomáš FOREJT Vojtěch KRČÁL Jan KŘETÍNSKÝ Jan KUČERA Antonín

Year of publication 2013
Type Article in Periodical
Magazine / Source Information and Computation
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1016/j.ic.2013.01.001
Field Informatics
Keywords continuous time stochastic systems; time-bounded reachability; stochastic games
Description 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 epsilon-optimal strategies in finite games and provide detailed complexity estimations. Moreover, we show how to compute epsilon-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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.