Continuous-time stochastic games with time-bounded reachability

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.

Authors

• Tomáš Brázdil
• Vojtěch Forejt
• Jan Krčál
• Jan Křetínský
• Antonín Kučera

Keywords

• Continuous time stochastic systems
• Time-bounded reachability
• Stochastic games