On strong determinacy of countable stochastic games
<p>We study 2-player turn-based perfect-information stochastic games with countably infinite state space. The players aim at maximizing/minimizing the probability of a given event (i.e., measurable set of infinite plays), such as reachability, Büchi, ω-regular or more general objectives.</p...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Published: |
Institute for Electrical and Electronics Engineers
2017
|
| _version_ | 1797100763944583168 |
|---|---|
| author | Kiefer, S Mayr, R Shirmohammadi, M Wojtczak, D |
| author_facet | Kiefer, S Mayr, R Shirmohammadi, M Wojtczak, D |
| author_sort | Kiefer, S |
| collection | OXFORD |
| description | <p>We study 2-player turn-based perfect-information stochastic games with countably infinite state space. The players aim at maximizing/minimizing the probability of a given event (i.e., measurable set of infinite plays), such as reachability, Büchi, ω-regular or more general objectives.</p> <br/> <p>These games are known to be weakly determined, i.e., they have value. However, strong determinacy of threshold objectives (given by an event ε and a threshold c ∈ [0, 1]) was open in many cases: is it always the case that the maximizer or the minimizer has a winning strategy, i.e., one that enforces, against all strategies of the other player, that ε is satisfied with probability ≥ c (resp. < c)?</p> <br/> <p>We show that almost-sure objectives (where c = 1) are strongly determined. This vastly generalizes a previous result on finite games with almost-sure tail objectives. On the other hand we show that ≥ 1/2 (co-)Büchi objectives are not strongly determined, not even if the game is finitely branching.</p> <br/> <p>Moreover, for almost-sure reachability and almost-sure Büchi objectives in finitely branching games, we strengthen strong determinacy by showing that one of the players must have a memoryless deterministic (MD) winning strategy.</p> |
| first_indexed | 2024-03-07T05:42:14Z |
| format | Conference item |
| id | oxford-uuid:e5f7bc7a-7581-44b9-bdf4-45bd0cc3326a |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:42:14Z |
| publishDate | 2017 |
| publisher | Institute for Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | oxford-uuid:e5f7bc7a-7581-44b9-bdf4-45bd0cc3326a2022-03-27T10:27:54ZOn strong determinacy of countable stochastic gamesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:e5f7bc7a-7581-44b9-bdf4-45bd0cc3326aSymplectic Elements at OxfordInstitute for Electrical and Electronics Engineers2017Kiefer, SMayr, RShirmohammadi, MWojtczak, D<p>We study 2-player turn-based perfect-information stochastic games with countably infinite state space. The players aim at maximizing/minimizing the probability of a given event (i.e., measurable set of infinite plays), such as reachability, Büchi, ω-regular or more general objectives.</p> <br/> <p>These games are known to be weakly determined, i.e., they have value. However, strong determinacy of threshold objectives (given by an event ε and a threshold c ∈ [0, 1]) was open in many cases: is it always the case that the maximizer or the minimizer has a winning strategy, i.e., one that enforces, against all strategies of the other player, that ε is satisfied with probability ≥ c (resp. < c)?</p> <br/> <p>We show that almost-sure objectives (where c = 1) are strongly determined. This vastly generalizes a previous result on finite games with almost-sure tail objectives. On the other hand we show that ≥ 1/2 (co-)Büchi objectives are not strongly determined, not even if the game is finitely branching.</p> <br/> <p>Moreover, for almost-sure reachability and almost-sure Büchi objectives in finitely branching games, we strengthen strong determinacy by showing that one of the players must have a memoryless deterministic (MD) winning strategy.</p> |
| spellingShingle | Kiefer, S Mayr, R Shirmohammadi, M Wojtczak, D On strong determinacy of countable stochastic games |
| title | On strong determinacy of countable stochastic games |
| title_full | On strong determinacy of countable stochastic games |
| title_fullStr | On strong determinacy of countable stochastic games |
| title_full_unstemmed | On strong determinacy of countable stochastic games |
| title_short | On strong determinacy of countable stochastic games |
| title_sort | on strong determinacy of countable stochastic games |
| work_keys_str_mv | AT kiefers onstrongdeterminacyofcountablestochasticgames AT mayrr onstrongdeterminacyofcountablestochasticgames AT shirmohammadim onstrongdeterminacyofcountablestochasticgames AT wojtczakd onstrongdeterminacyofcountablestochasticgames |