Abstract | ||
---|---|---|
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 @e-optimal strategies in finite games and provide detailed complexity estimations. Moreover, we show how to compute @e-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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.ic.2013.01.001 | Information & Computation |
Keywords | Field | DocType |
bounded rate,continuous-time stochastic game,detailed complexity estimation,time-abstract strategy,finite uniform game,e-optimal strategy,infinite game,time-bounded reachability,finite game,optimal strategy,equilibrium probability,reachability | Discrete mathematics,Combinatorics,Vertex (geometry),Reachability,Mathematics,Bounded function | Journal |
Volume | ISSN | Citations |
224, | 0890-5401 | 13 |
PageRank | References | Authors |
0.66 | 13 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomáš Brázdil | 1 | 194 | 13.11 |
Vojtech Forejt | 2 | 302 | 14.69 |
Jan Krčál | 3 | 79 | 7.45 |
Jan Křetínský | 4 | 190 | 12.05 |
Antonín Kučera | 5 | 262 | 18.04 |