Continuous-Time Stochastic Games with Time-Bounded Reachability
| Authors | |
|---|---|
| Year of publication | 2013 |
| Type | Article in Periodical |
| Magazine / Source | Information and Computation |
| MU Faculty or unit | |
| Citation | |
| Doi | https://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: |