z-logo
open-access-imgOpen Access
Pure Strategies in Imperfect Information Stochastic Games
Author(s) -
Arnaud Carayol,
Christof Löding,
Olivier Serre
Publication year - 2018
Publication title -
fundamenta informaticae
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.311
H-Index - 67
eISSN - 1875-8681
pISSN - 0169-2968
DOI - 10.3233/fi-2018-1687
Subject(s) - perfect information , imperfect , mathematical economics , computer science , mathematics , linguistics , philosophy
We consider imperfect information stochastic games where we require the players to use pure (i.e. non randomised) strategies. We consider reachability, safety, B\"uchi and co-B\"uchi 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\"uchi with optimal algorithms to decide existence of a pure winning strategy and to compute one if 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom