-
Selection by year
-
Selection by authors
-
Complete lists
lics09
N. Bertrand, B. Genest, Gimbert. H.. Qualitative Determinacy and Decidability of Stochastic Games with Signals. In 24th Annual IEEE Symposium on Logic in Computer Science (LICS'09), Pages 319-328, Los Angeles, CA, USA, August 2009.
Download [help]
Download paper:
Doi page 
Download paper:
Adobe portable document (pdf) 
Copyright notice:
This material is presented to ensure timely dissemination of scholarly and
technical work. Copyright and all rights therein are retained by authors or
by other copyright holders. All persons copying this information are expected
to adhere to the terms and constraints invoked by each author's
copyright. These works may not be reposted without the explicit permission of
the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic
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, Büchi or co-Büchi 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 Büchi game if player 1 cannot achieve almost-surely the Büchi objective, then player 2 can ensure positively the complementary co-Büchi 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
Contact
Nathalie Bertrand http://www.irisa.fr/prive/nbertran/
Blaise Genest http://perso.crans.org/~genest/
BibTex Reference
@InProceedings{lics09,
Author = {Bertrand, N. and Genest, B. and H, Gimbert.},
Title = {Qualitative Determinacy and Decidability of Stochastic Games with Signals},
BookTitle = {24th Annual IEEE Symposium on Logic in Computer Science (LICS'09)},
Pages = {319--328},
Publisher = {IEEE Computer Society Press},
Address = {Los Angeles, CA, USA},
Month = {August},
Year = {2009}
}
EndNote Reference [help]
Get EndNote Reference (.ref)