Continuous-Time Stochastic Games with Time-Bounded Reachability
by
Tomáš Brázdil,
Vojtěch Forejt,
Jan Krčál,
Jan Křetínský,
Antonín Kučera,
A full version of the paper presented at FST&TCS 2009. October 2009, 46 pages.
FIMU-RS-2009-09.
Available as Postscript,
PDF.
Abstract:
We study continuous-time stochastic games with
time-bounded reachability objectives. 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.
Finally, we show how to compute optimal strategies in finite uniform
games, and how to compute e-optimal strategies in
finitely-branching games with bounded rates (for finite games, we
provide detailed complexity estimations).