{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T22:30:14Z","timestamp":1779143414809,"version":"3.51.4"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2017,9,15]],"date-time":"2017-09-15T00:00:00Z","timestamp":1505433600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR projet STOCH-MC","award":["ANR-13-BS02-0011-01"],"award-info":[{"award-number":["ANR-13-BS02-0011-01"]}]},{"name":"ESF Research Networking Programme","award":["GAMES2"],"award-info":[{"award-number":["GAMES2"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>We consider two-person zero-sum stochastic games with signals, a standard model of stochastic games with imperfect information. The only source of information for the players consists of the signals they receive; they cannot directly observe the state of the game, nor the actions played by their opponent, nor their own actions.<\/jats:p>\n          <jats:p>\n            We are interested in the existence of almost-surely winning or positively winning strategies, under reachability, safety, B\u00fcchi, or co-B\u00fcchi winning objectives, and the computation of these strategies when the game has finitely many states and actions. We prove two\n            <jats:italic>qualitative determinacy<\/jats:italic>\n            results. First, in a reachability game, either player 1 can achieve almost surely the reachability objective, or player 2 can achieve surely the dual safety objective, or both players have positively winning strategies. Second, in a B\u00fcchi game, if player 1 cannot achieve almost surely the B\u00fcchi objective, then player 2 can ensure positively the dual co-B\u00fcchi objective. We prove that players only need strategies with\n            <jats:italic>finite memory<\/jats:italic>\n            . The number of memory states needed to win with finite-memory strategies ranges from one (corresponding to memoryless strategies) to doubly exponential, with matching upper and lower bounds. Together with the qualitative determinacy results, we also provide fix-point algorithms for deciding which player has an almost-surely winning or a positively winning strategy and for computing an associated finite-memory strategy. Complexity ranges from EXPTIME to 2EXPTIME, with matching lower bounds. Our fix-point algorithms also enjoy a better complexity in the cases where one of the players is better informed than their opponent.\n          <\/jats:p>\n          <jats:p>Our results hold even when players do not necessarily observe their own actions. The adequate class of strategies, in this case, is mixed or general strategies (they are equivalent). Behavioral strategies are too restrictive to guarantee determinacy: it may happen that one of the players has a winning general strategy but none of them has a winning behavioral strategy. On the other hand, if a player can observe their actions, then general, mixed, and behavioral strategies are equivalent. Finite-memory strategies are sufficient for determinacy to hold, provided that randomized memory updates are allowed.<\/jats:p>","DOI":"10.1145\/3107926","type":"journal-article","created":{"date-parts":[[2017,9,15]],"date-time":"2017-09-15T12:20:54Z","timestamp":1505478054000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Qualitative Determinacy and Decidability of Stochastic Games with Signals"],"prefix":"10.1145","volume":"64","author":[{"given":"Nathalie","family":"Bertrand","sequence":"first","affiliation":[{"name":"INRIA, Centre Bretagne Atlantique, IRISA"}]},{"given":"Blaise","family":"Genest","sequence":"additional","affiliation":[{"name":"CNRS, IRISA"}]},{"given":"Hugo","family":"Gimbert","sequence":"additional","affiliation":[{"name":"CNRS, Universit\u00e9 de Bordeaux, LaBRI"}]}],"member":"320","published-online":{"date-parts":[[2017,9,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Mixed and behaviour strategies in infinite extensive games","author":"Aumann R. J.","year":"1964","unstructured":"R. J. Aumann . 1964. Mixed and behaviour strategies in infinite extensive games . 1964 . In Advances in Game Theory, Annals of Mathematics Studies, Dresher, Shapley 8 Tucker (Eds.). vol. 52 , Princeton University Press , 627--650. R. J. Aumann. 1964. Mixed and behaviour strategies in infinite extensive games. 1964. In Advances in Game Theory, Annals of Mathematics Studies, Dresher, Shapley 8 Tucker (Eds.). vol. 52, Princeton University Press, 627--650."},{"key":"e_1_2_1_2_1","volume-title":"Repeated Games with Incomplete Information","author":"Aumann R. J.","unstructured":"R. J. Aumann . 1995. Repeated Games with Incomplete Information . MIT Press . R. J. Aumann. 1995. Repeated Games with Incomplete Information. MIT Press."},{"key":"e_1_2_1_3_1","volume-title":"Proc. of FOSSACS\u201908 (LNCS)","volume":"4972","author":"Baier C.","unstructured":"C. Baier , N. Bertrand , and M. Gr\u00f6\u00dfer . 2008. On decision problems for probabilistic B\u00fcchi automata . In Proc. of FOSSACS\u201908 (LNCS) , Vol. 4972 . Springer, 287--301. C. Baier, N. Bertrand, and M. Gr\u00f6\u00dfer. 2008. On decision problems for probabilistic B\u00fcchi automata. In Proc. of FOSSACS\u201908 (LNCS), Vol. 4972. Springer, 287--301."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.31"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85361-9_27"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.02.002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_71"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2012.28"},{"key":"e_1_2_1_9_1","volume-title":"Proc. of MFCS\u201910 (LNCS)","volume":"6281","author":"Chatterjee K.","unstructured":"K. Chatterjee , L. Doyen , H. Gimbert , and T. A. Henzinger . 2010. Randomness for free . In Proc. of MFCS\u201910 (LNCS) , Vol. 6281 . Springer, 246--257. K. Chatterjee, L. Doyen, H. Gimbert, and T. A. Henzinger. 2010. Randomness for free. In Proc. of MFCS\u201910 (LNCS), Vol. 6281. Springer, 246--257."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-012-0164-2"},{"key":"e_1_2_1_11_1","volume-title":"Algorithms for omega-regular games of incomplete information. Logical Methods in Computer Science 3, 3","author":"Chatterjee K.","year":"2007","unstructured":"K. Chatterjee , L. Doyen , T. A. Henzinger , and J.-F. Raskin . 2007. Algorithms for omega-regular games of incomplete information. Logical Methods in Computer Science 3, 3 ( 2007 ). K. Chatterjee, L. Doyen, T. A. Henzinger, and J.-F. Raskin. 2007. Algorithms for omega-regular games of incomplete information. Logical Methods in Computer Science 3, 3 (2007)."},{"key":"e_1_2_1_12_1","volume-title":"Proc. of SODA\u201904","author":"Chatterjee K.","unstructured":"K. Chatterjee , M. Jurdzinski , and T. A. Henzinger . 2004. Quantitative stochastic parity games . In Proc. of SODA\u201904 . SIAM, 121--130. K. Chatterjee, M. Jurdzinski, and T. A. Henzinger. 2004. Quantitative stochastic parity games. In Proc. of SODA\u201904. SIAM, 121--130."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings First Symposium on Games, Automata, Logic, and Formal Verification (GANDALF\u201910)","author":"Cristau J.","unstructured":"J. Cristau , C. David , and F. Horn . 2010. How do we remember the past in randomised strategies? In Proceedings First Symposium on Games, Automata, Logic, and Formal Verification (GANDALF\u201910) . 30--39. J. Cristau, C. David, and F. Horn. 2010. How do we remember the past in randomised strategies? In Proceedings First Symposium on Games, Automata, Logic, and Formal Verification (GANDALF\u201910). 30--39."},{"key":"e_1_2_1_15_1","volume-title":"Proc. of LICS\u201900","author":"de Alfaro L.","unstructured":"L. de Alfaro and T. A. Henzinger . 2000. Concurrent omega-regular games . In Proc. of LICS\u201900 . IEEE, 141--154. L. de Alfaro and T. A. Henzinger. 2000. Concurrent omega-regular games. In Proc. of LICS\u201900. IEEE, 141--154."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.008"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380871"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511779398"},{"key":"e_1_2_1_19_1","volume-title":"Proc. of FOSSACS\u201908 (LNCS)","volume":"4972","author":"Gimbert H.","unstructured":"H. Gimbert and F. Horn . 2008. Simple stochastic games with few random vertices are easy to solve . In Proc. of FOSSACS\u201908 (LNCS) , Vol. 4972 . Springer, 5--19. H. Gimbert and F. Horn. 2008. Simple stochastic games with few random vertices are easy to solve. In Proc. of FOSSACS\u201908 (LNCS), Vol. 4972. Springer, 5--19."},{"key":"e_1_2_1_20_1","volume-title":"Proc. of the 37th International Colloquium on Automata, Languages and Programming (ICALP\u201910)","volume":"6199","author":"Gimbert H.","unstructured":"H. Gimbert and Y. Oualhadj . 2010. Probabilistic automata on finite words: Decidable and undecidable problems . In Proc. of the 37th International Colloquium on Automata, Languages and Programming (ICALP\u201910) (Lecture Notes in Computer Science) , Vol. 6199 . Springer, 527--538. H. Gimbert and Y. Oualhadj. 2010. Probabilistic automata on finite words: Decidable and undecidable problems. In Proc. of the 37th International Colloquium on Automata, Languages and Programming (ICALP\u201910) (Lecture Notes in Computer Science), Vol. 6199. Springer, 527--538."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AAP1095"},{"key":"e_1_2_1_22_1","volume-title":"Logics and Infinite Games. LNCS","volume":"2500","author":"Gr\u00e4del E.","unstructured":"E. Gr\u00e4del , W. Thomas , and T. Wilke . 2002. Automata , Logics and Infinite Games. LNCS , Vol. 2500 . Springer. E. Gr\u00e4del, W. Thomas, and T. Wilke. 2002. Automata, Logics and Infinite Games. LNCS, Vol. 2500. Springer."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_17"},{"key":"e_1_2_1_24_1","unstructured":"V. Gripon and O. Serre. 2011. Qualitative concurrent stochastic games with imperfect information. CoRR abs\/0902.2108 (2011).  V. Gripon and O. Serre. 2011. Qualitative concurrent stochastic games with imperfect information. CoRR abs\/0902.2108 (2011)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2307\/2586667"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.79.6.2145"},{"key":"e_1_2_1_28_1","volume-title":"Introduction to Probabilistic Automata","author":"Paz A.","unstructured":"A. Paz . 1971. Introduction to Probabilistic Automata . Academic Press . A. Paz. 1971. Introduction to Probabilistic Automata. Academic Press."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(63)90290-0"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804422"},{"key":"e_1_2_1_32_1","unstructured":"J. Renault and S. Sorin. 2008. Personal Communications. (2008).  J. Renault and S. Sorin. 2008. Personal Communications. (2008)."},{"key":"e_1_2_1_33_1","volume-title":"Technical Report 1376. Northwestern University.","author":"Rosenberg D.","year":"2003","unstructured":"D. Rosenberg , E. Solan , and N. Vieille . 2003 . Stochastic Games with Imperfect Monitoring . Technical Report 1376. Northwestern University. D. Rosenberg, E. Solan, and N. Vieille. 2003. Stochastic Games with Imperfect Monitoring. Technical Report 1376. Northwestern University."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.39.10.1953"},{"key":"e_1_2_1_35_1","volume-title":"A First Course on Zero-Sum Repeated Games","author":"Sorin S.","unstructured":"S. Sorin . 2002. A First Course on Zero-Sum Repeated Games . Springer . S. Sorin. 2002. A First Course on Zero-Sum Repeated Games. Springer."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.12.038"},{"key":"e_1_2_1_37_1","unstructured":"J. von Neumann and O. Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton University Press.  J. von Neumann and O. Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton University Press."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3107926","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3107926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:25Z","timestamp":1750217425000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3107926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,15]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3107926"],"URL":"https:\/\/doi.org\/10.1145\/3107926","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,15]]},"assertion":[{"value":"2013-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}