2009, English, Article edition: Qualitative Determinacy and Decidability of Stochastic Games with Signals Bertrand, Nathalie; Genest, Blaise; Gimbert, Hugo

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/207072
Physical Description
  • text
Published
  • HAL - CCSD
  • 2009
Language
  • English

Edition details

Title
  • Qualitative Determinacy and Decidability of Stochastic Games with Signals
Author
  • Bertrand, Nathalie
  • Genest, Blaise
  • Gimbert, Hugo
Published
  • HAL - CCSD
  • 2009
Physical Description
  • text
Subjects
Notes
  • 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 \emph{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.
  • HAL:hal-00356566, version 1
  • HAL:http:/​/​hal.archives-ouvertes.fr/​hal-00356566/​en/​
Language
  • English
Contributed by
OAIster

Get this edition

  • Set up My libraries

    How do I set up "My libraries"?

    In order to set up a list of libraries that you have access to, you must first login or sign up. Then set up a personal list of libraries from your profile page by clicking on your user name at the top right of any screen.

  • All (1)
  • Unknown (1)
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment