Pure Strategies in Imperfect Information Stochastic Games

Article type: Research Article

Authors: Carayol, Arnaud^a | Löding, Christof^b | Serre, Olivier^{c; *}

Affiliations: [a] Université Paris-Est, LIGM (UMR 8049), CNRS, ENPC, ESIEE Paris, UPEM, France. [email protected] | [b] Informatik 7, RWTH Aachen, Germany. [email protected] | [c] IRIF (CNRS & Université Paris Diderot–Paris 7), France. [email protected]

Correspondence: [*] Address for correspondence: IRIF, Université Paris Diderot–Paris 7, Case 7014, 75205 PARIS Cedex 13 France.

Abstract: We consider imperfect information stochastic games where we require the players to use pure (i.e. non randomised) strategies. We consider reachability, safety, Büchi and co-Büchi objectives, and investigate the existence of almost-sure/positively winning strategies for the first player when the second player is perfectly informed or more informed than the first player. We obtain decidability results for positive reachability and almost-sure Büchi with optimal algorithms to decide existence of a pure winning strategy and to compute one if it exists. We complete the picture by showing that positive safety is undecidable when restricting to pure strategies even if the second player is perfectly informed.

Keywords: Two-player imperfect information stochastic games, pure strategies, decidability/undecidability

DOI: 10.3233/FI-2018-1687

Journal: Fundamenta Informaticae, vol. 160, no. 4, pp. 361-384, 2018