Skip to Main content Skip to Navigation
Journal articles

Qualitative Determinacy and Decidability of Stochastic Games with Signals

Abstract : We consider two-person zero-sum stochastic games with signals, a standard model of stochastic games with imperfect information. The only source of information for the players consists of the signals they receive; they cannot directly observe the state of the game, nor the actions played by their opponent, nor their own actions. 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, and the computation of these strategies when the game has finitely many states and actions. 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 achieve surely the dual 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 dual co-Büchi objective. We prove that players only need strategies with finite memory. The number of memory states needed to win with finite-memory strategies ranges from one (corresponding to memoryless strategies) to doubly exponential, with matching upper and 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 an associated finite-memory strategy. Complexity ranges from EXPTIME to 2EXPTIME, with matching lower bounds. Our fix-point algorithms also enjoy a better complexity in the cases where one of the players is better informed than their opponent. Our results hold even when players do not necessarily observe their own actions. The adequate class of strategies, in this case, is mixed or general strategies (they are equivalent). Behavioral strategies are too restrictive to guarantee determinacy: it may happen that one of the players has a winning general strategy but none of them has a winning behavioral strategy. On the other hand, if a player can observe their actions, then general, mixed, and behavioral strategies are equivalent. Finite-memory strategies are sufficient for determinacy to hold, provided that randomized memory updates are allowed.
Document type :
Journal articles
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/hal-01635127
Contributor : Nathalie Bertrand <>
Submitted on : Thursday, November 16, 2017 - 3:47:40 PM
Last modification on : Tuesday, December 8, 2020 - 9:39:07 AM
Long-term archiving on: : Saturday, February 17, 2018 - 12:46:30 PM

File

final_version.pdf
Files produced by the author(s)

Identifiers

Citation

Nathalie Bertrand, Blaise Genest, Hugo Gimbert. Qualitative Determinacy and Decidability of Stochastic Games with Signals. Journal of the ACM (JACM), Association for Computing Machinery, 2017, 64 (5), pp.33:1 - 33:48. ⟨10.1145/3107926⟩. ⟨hal-01635127⟩

Share

Metrics

Record views

913

Files downloads

262