Continuous-Time Stochastic Games with Time-Bounded Reachability

Tomas Brazdil, Vojtech Forejt, Jan Krcal, Jan Kretinsky & Antonin Kucera
We study continuous-time stochastic games with time-bounded reachability objectives. We show that each vertex in such a game has a \emph{value} (i.e., an equilibrium probability), and we classify the conditions under which optimal strategies exist. Finally, we show how to compute optimal strategies in finite uniform games, and how to compute $\varepsilon$-optimal strategies in finitely-branching games with bounded rates (for finite games, we provide detailed complexity estimations).