Pure Strategies in Imperfect Information Stochastic Games

• Autorzy: Carayol A. , Löding C. , Serre O.

Identyfikatory

DOI

10.3233/FI-2018-1687

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

two-player imperfect information stochastic games; stochastic games; pure strategies; decidability; undecidability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 160, nr 4
• Strony: 361--384
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Carayol A.

• Université Paris-Est, LIGM (UMR 8049), CNRS, ENPC, ESIEE Paris, UPEM, France

autor

Löding C.

• Informatik 7, RWTH Aachen, Germany

autor

Serre O.

• IRIF (CNRS & Université Paris Diderot–Paris 7, France

Bibliografia

• [1] de Alfaro L, Henzinger T. Concurrent Omega-Regular Games, Proceedings of Logic in Computer Science (LiCS’00), IEEE Computer Society, 2000. doi:10.1109/LICS.2000.855763.
• [2] de Alfaro L, Henzinger TA, Kupferman O. Concurrent reachability games, Theoretical Computer Science, 2007;386(3):188-217. URL https://doi.org/10.1016/j.tcs.2007.07.008.
• [3] Baier C, Bertrand N, Größer M. On Decision Problems for Probabilistic Büchi Automata, Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2008), 4962, Springer-Verlag, 2008. doi:10.1007/978-3-540-78499-9_21.
• [4] Bertrand N, Genest B, Gimbert H. Qualitative Determinacy and Decidability of Stochastic Games with Signals, Proceedings of Logic in Computer Science (LiCS’09), IEEE Computer Society, 2009. doi:10.1145/3107926.
• [5] Bertrand N, Genest B, Gimbert H. Qualitative Determinacy and Decidability of Stochastic Games with Signals, Journal of the Association for Computing Machinery (ACM), 2017;64(5):33/1-33/48.doi:10.1145/3107926.
• [6] Berwanger D, Doyen L. On the Power of Imperfect Information, Proceedings of the 28th International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2008), 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008. URL http://drops.dagstuhl.de/opus/volltexte/2008/1742.
• [7] Carayol A, Haddad A, Serre O. Randomisation in Automata on Infinite Trees, ACM Transactions on Computational Logic, 2014;15(3):38. doi:10.1145/2629336.
• [8] Chatterjee K. Stochastic ω-Regular Games, Ph.D. Thesis, University of California, 2007.
• [9] Chatterjee K, Doyen L. Partial-Observation Stochastic Games: How to Win when Belief Fails, ACM Transactions on Computational Logic, 2014;15(2):16. doi:10.1109/LICS.2012.28.
• [10] Chatterjee K, Doyen L, Henzinger T, Raskin JF. Algorithms for Omega-Regular Games with Imperfect Information, LMCS, 2007;3(3):287-302. doi:10.1007/11874683_19.
• [11] Fijalkow N, Pinchinat S, Serre O. Emptiness Of Alternating Tree Automata Using Games With Imperfect Information, Proceedings of the 33rd International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2013), 24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. doi:10.4230/LIPIcs.FSTTCS.2013.299.
• [12] Gimbert H, Oualhadj Y. Probabilistic Automata on Finite Words: Decidable and Undecidable Problems, Proceedings of the 37th International Colloquium on Automata, Languages, and Programming (ICALP 2010), 6199, Springer-Verlag, 2010, pp. 527-538. doi:10.1007/978-3-642-14162-1_44.
• [13] Gripon V, Serre O. Qualitative Concurrent Stochastic Games with Imperfect Information, Proceedings of the 36th International Colloquium on Automata, Languages, and Programming (ICALP 2009), 5556, Springer-Verlag, 2009, pp. 200-211. doi:10.1007/978-3-642-02930-1_17.
• [14] Paz A. Introduction to probabilistic automata, Academic Press New York, 1971. ISBN:0125476507.
• [15] Ramadge P, Wonham W. Supervisory Control of a Class of Discrete Event Processes, SIAM Journal on Control and Optimization, 25, 1987, 206. doi:10.1007/BFb0006306.
• [16] Reif J. The Complexity of Two-Player Games of Incomplete Information, Journal of Computer and System Sciences, 1984;29(2):274-301. URL https://doi.org/10.1016/0022-0000(84)90034-5.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).