pith. sign in

arxiv: 1506.09140 · v2 · pith:H2ZUTT5Fnew · submitted 2015-06-30 · 💻 cs.FL · cs.GT

Pure Strategies in Imperfect Information Stochastic Games

classification 💻 cs.FL cs.GT
keywords playerpurestrategiesinformeduchialmost-sureconsiderexistence
0
0 comments X
read the original 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\"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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.