Name
Abstract | ||
|---|---|---|
We consider the standard model of finite two-person zero-sum stochastic games with signals. We are interested in the existence of almost-surely winning or positively winning strategies, under reachability, safety, Buchi or co-Buchi winning objectives. We prove two qualitative determinacy results. First, in a reachability game either player $1$ can achieve almost-surely the reachability objective, or player 2 can ensure surely the complementary safety objective, or both players have positively winning strategies. Second, in a Buchi game if player 1 cannot achieve almost-surely the Buchi objective, then player 2 can ensure positively the complementary co-Buchi objective. We prove that players only need strategies with finite-memory, whose sizes range from no memory at all to doubly-exponential number of states, with matching lower bounds. Together with the qualitative determinacy results, we also provide fix-point algorithms for deciding which player has an almost-surely winning or a positively winning strategy and for computing the finite memory strategy. Complexity ranges from EXPTIME to 2-EXPTIME with matching lower bounds, and better complexity can be achieved for some special cases where one of the players is better informed than her opponent. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/LICS.2009.31 | J. ACM |
Keywords | Field | DocType |
reachability objective,buchi game,qualitative determinacy,almost-surely winning,stochastic games,complementary co-buchi objective,better complexity,lower bound,buchi objective,reachability game,complementary safety objective,qualitative determinacy result,fixed point,stochastic processes,imperfect information,games,common sense reasoning,determinacy,standard model,signals,data mining | Discrete mathematics,Combinatorics,EXPTIME,Computer science,Commonsense reasoning,Stochastic process,Decidability,Reachability,Perfect information,Determinacy | Conference |
Volume | Issue | ISSN |
64 | 5 | 0004-5411 |
Citations | PageRank | References |
23 | 1.05 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nathalie Bertrand | 1 | 250 | 17.84 |
| Blaise Genest | 2 | 304 | 25.09 |
| Hugo Gimbert | 3 | 249 | 21.31 |