{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:48Z","timestamp":1750219788115,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM SIGLOG News"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:p>This article is a tutorial introduction to stochastic games, first introduced by Shapley in 1953. The presentation is based around several classical examples of such games, and focusses on the question of strategy complexity in terms of parameters such as the cardinality of the state space, branching factor of the transition function, and whether the game is concurrent or turn-based. Our goal is to give a practical introduction to stochastic games, the notion of values and strategies, and the memory requirements of optimal and \u03b5-optimal strategies in different games.<\/jats:p>","DOI":"10.1145\/3583660.3583666","type":"journal-article","created":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:06:21Z","timestamp":1675703181000},"page":"27-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Beginner's Tutorial on Strategy Complexity in Stochastic Games"],"prefix":"10.1145","volume":"9","author":[{"given":"Mahsa","family":"Shirmohammadi","sequence":"first","affiliation":[{"name":"CNRS &amp; IRIF, Paris"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"E. Altman K. Avrachenkov N. Bonneau M. Debbah R. El-Azouzi and D. Menasche. 2007. Constrained stochastic games in wireless networks. In IEEE global communications conference (GLOBECOM) IEEE (Ed.). Washington.  E. Altman K. Avrachenkov N. Bonneau M. Debbah R. El-Azouzi and D. Menasche. 2007. Constrained stochastic games in wireless networks. In IEEE global communications conference (GLOBECOM) IEEE (Ed.). Washington.","DOI":"10.1109\/GLOCOM.2007.66"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00186-005-0034-4"},{"volume-title":"Economics and the Theory of Games","author":"Bacharach M.","key":"e_1_2_1_3_1","unstructured":"M. Bacharach . 2019. Economics and the Theory of Games . CRC Press . M. Bacharach. 2019. Economics and the Theory of Games. CRC Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3107926"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177698513"},{"key":"e_1_2_1_6_1","volume-title":"Languages and Programming (ICALP) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"55","author":"Bouyer P.","unstructured":"P. Bouyer , N. Markey , M. Randour , A. Sangnier , and D. Stan . 2016. Reachability in Networks of Register Protocols under Stochastic Schedulers. In International Colloquium on Automata , Languages and Programming (ICALP) (Leibniz International Proceedings in Informatics (LIPIcs)) , Vol. 55 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 106:1--106:14. P. Bouyer, N. Markey, M. Randour, A. Sangnier, and D. Stan. 2016. Reachability in Networks of Register Protocols under Stochastic Schedulers. In International Colloquium on Automata, Languages and Programming (ICALP) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 55. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 106:1--106:14."},{"volume-title":"Zero-Reachability in Probabilistic Multi-Counter Automata. In ACM\/IEEE Symposium on Logic in Computer Science (LICS) (CSL-LICS '14)","author":"Br\u00e1zdil T.","key":"e_1_2_1_7_1","unstructured":"T. Br\u00e1zdil , S. Kiefer , A. Ku\u010dera , P. Novotn\u00fd , and J.P. Katoen . 2014 . Zero-Reachability in Probabilistic Multi-Counter Automata. In ACM\/IEEE Symposium on Logic in Computer Science (LICS) (CSL-LICS '14) . Association for Computing Machinery, New York, NY, USA, Article 22, 10 pages. T. Br\u00e1zdil, S. Kiefer, A. Ku\u010dera, P. Novotn\u00fd, and J.P. Katoen. 2014. Zero-Reachability in Probabilistic Multi-Counter Automata. In ACM\/IEEE Symposium on Logic in Computer Science (LICS) (CSL-LICS '14). Association for Computing Machinery, New York, NY, USA, Article 22, 10 pages."},{"volume-title":"International Conference on TOOLS and Algorithms for the Construction and Analysis of Systems. Springer, 185--191","author":"Chen T.","key":"e_1_2_1_8_1","unstructured":"T. Chen , V. Forejt , M. Kwiatkowska , D. Parker , and A. Simaitis . 2013. PRISM-games: A model checker for stochastic multi-player games . In International Conference on TOOLS and Algorithms for the Construction and Analysis of Systems. Springer, 185--191 . T. Chen, V. Forejt, M. Kwiatkowska, D. Parker, and A. Simaitis. 2013. PRISM-games: A model checker for stochastic multi-player games. In International Conference on TOOLS and Algorithms for the Construction and Analysis of Systems. Springer, 185--191."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1051\/ps:1997104","article-title":"A note on \"Big-Match","volume":"1","author":"Coulomb J. M.","year":"1997","unstructured":"J. M. Coulomb . 1997 . A note on \"Big-Match \". ESAIM: Probability and Statistics 1 (1997), 89 -- 93 . http:\/\/eudml.org\/doc\/104243 J. M. Coulomb. 1997. A note on \"Big-Match\". ESAIM: Probability and Statistics 1 (1997), 89--93. http:\/\/eudml.org\/doc\/104243","journal-title":"ESAIM: Probability and Statistics"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/503209"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743507"},{"volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller W.","key":"e_1_2_1_13_1","unstructured":"W. Feller . 1966. An Introduction to Probability Theory and Its Applications ( second ed.). Vol. 1 . Wiley & Sons . W. Feller. 1966. An Introduction to Probability Theory and Its Applications (second ed.). Vol. 1. Wiley & Sons."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00935890"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1007\/s13235-021-00378-z","article-title":"Subgame Maxmin Strategies in Zero-Sum Stochastic Games with Tolerance Levels","volume":"11","author":"Flesch J.","year":"2021","unstructured":"J. Flesch , P. J. Herings , J. Maes , and A. Predtetchinski . 2021 . Subgame Maxmin Strategies in Zero-Sum Stochastic Games with Tolerance Levels . Dynamic Games and Applications 11 , 4 (2021), 704 -- 737 . J. Flesch, P. J. Herings, J. Maes, and A. Predtetchinski. 2021. Subgame Maxmin Strategies in Zero-Sum Stochastic Games with Tolerance Levels. Dynamic Games and Applications 11, 4 (2021), 704--737.","journal-title":"Dynamic Games and Applications"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1017\/jpr.2018.47","article-title":"Characterization and simplification of optimal strategies in positive stochastic games","volume":"55","author":"Flesch J.","year":"2018","unstructured":"J. Flesch , A. Predtetchinski , and W. D. Sudderth . 2018 . Characterization and simplification of optimal strategies in positive stochastic games . Journal of Applied Probability 55 , 3 (2018), 728 -- 741 . J. Flesch, A. Predtetchinski, and W. D. Sudderth. 2018. Characterization and simplification of optimal strategies in positive stochastic games. Journal of Applied Probability 55, 3 (2018), 728--741.","journal-title":"Journal of Applied Probability"},{"key":"e_1_2_1_18_1","unstructured":"L. Fortnow and P. G. Kimmel. 1998. Beating a Finite Automaton in the Big Match.. In TARK. 225--234.  L. Fortnow and P. G. Kimmel. 1998. Beating a Finite Automaton in the Big Match.. In TARK. 225--234."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882151-011"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219198"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"K. A. Hansen R. Ibsen-Jensen and M. Kouck\u00fd. 2016. The Big Match in Small Space. In Algorithmic Game Theory. Springer Berlin Heidelberg 64--76.  K. A. Hansen R. Ibsen-Jensen and M. Kouck\u00fd. 2016. The Big Match in Small Space. In Algorithmic Game Theory. Springer Berlin Heidelberg 64--76.","DOI":"10.1007\/978-3-662-53354-3_6"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13235-011-0013-8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2020.7"},{"key":"e_1_2_1_25_1","unstructured":"S. Kiefer R. Mayr M. Shirmohammadi and P. Totzke. 2022. Strategy Complexity of Reachability in Countable Stochastic 2-Player Games. CoRR abs\/2203.12024 (2022).  S. Kiefer R. Mayr M. Shirmohammadi and P. Totzke. 2022. Strategy Complexity of Reachability in Countable Stochastic 2-Player Games. CoRR abs\/2203.12024 (2022)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005134"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0319039"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511973468.006"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13235-012-0054-7"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001820050071"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1070.0264"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"A. P. Maitra and W. D. Sudderth. 1996. Discrete Gambling and Stochastic Games. Springer New York New York NY.  A. P. Maitra and W. D. Sudderth. 1996. Discrete Gambling and Stochastic Games. Springer New York New York NY.","DOI":"10.1007\/978-1-4612-4002-0"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.2307\/1971035"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01769259"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-010-0189-2"},{"volume-title":"Advances in dynamic games : applications to economics, finance, optimization, and stochastic control","author":"Nowak A.","key":"e_1_2_1_37_1","unstructured":"A. Nowak . 2005. Advances in dynamic games : applications to economics, finance, optimization, and stochastic control . Birkhaeuser , Boston . A. Nowak. 2005. Advances in dynamic games : applications to economics, finance, optimization, and stochastic control. Birkhaeuser, Boston."},{"volume-title":"Theory and Decision Library (Game Theory, Mathematical Programming and Operations Research)","author":"Nowak A.S.","key":"e_1_2_1_38_1","unstructured":"A.S. Nowak and T.E.S. Raghavan . 1991. Positive Stochastic Games and a Theorem of Ornstein . In Stochastic Games And Related Topics, T.E.S Raghavan, T.S. Ferguson, T. Parthasarathy, and O.J. Vrieze (Eds.). Theory and Decision Library (Game Theory, Mathematical Programming and Operations Research) , Vol. 7 . Springer . A.S. Nowak and T.E.S. Raghavan. 1991. Positive Stochastic Games and a Theorem of Ornstein. In Stochastic Games And Related Topics, T.E.S Raghavan, T.S. Ferguson, T. Parthasarathy, and O.J. Vrieze (Eds.). Theory and Decision Library (Game Theory, Mathematical Programming and Operations Research), Vol. 7. Springer."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.2307\/2035700"},{"key":"e_1_2_1_40_1","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman M. L.","unstructured":"M. L. Puterman . 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming ( 1 st ed.). John Wiley & Sons, Inc. , New York, NY, USA . M. L. Puterman. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming (1st ed.). John Wiley & Sons, Inc., New York, NY, USA.","edition":"1"},{"key":"e_1_2_1_41_1","unstructured":"T. Raghaven T.S. Ferguson T. Parthasarathy and O. Vrieze. 2012. Stochastic games and related topics: in honor of Professor LS Shapley. Vol. 7. Springer Science & Business Media.  T. Raghaven T.S. Ferguson T. Parthasarathy and O. Vrieze. 2012. Stochastic games and related topics: in honor of Professor LS Shapley. Vol. 7. Springer Science & Business Media."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.2.494"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.39.10.1953"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1513508112"},{"volume-title":"Handbook of Game Theory with Economic Applications","author":"Sorin S.","key":"e_1_2_1_45_1","unstructured":"S. Sorin . 1992. Repeated games with complete information . In Handbook of Game Theory with Economic Applications , R. J. Aumann and S. Hart (Eds.). Handbook of Game Theory with Economic Applications, Vol. 1 . Elsevier , Chapter 4, 71--107. https:\/\/ideas.repec.org\/h\/eee\/gamchp\/1-04.html S. Sorin. 1992. Repeated games with complete information. In Handbook of Game Theory with Economic Applications, R. J. Aumann and S. Hart (Eds.). Handbook of Game Theory with Economic Applications, Vol. 1. Elsevier, Chapter 4, 71--107. https:\/\/ideas.repec.org\/h\/eee\/gamchp\/1-04.html"},{"volume-title":"A first course on zero-sum repeated games","author":"Sorin S.","key":"e_1_2_1_46_1","unstructured":"S. Sorin . 2002. A first course on zero-sum repeated games . Springer-Verlag , Berlin New York. S. Sorin. 2002. A first course on zero-sum repeated games. Springer-Verlag, Berlin New York."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejcon.2016.04.009"},{"volume-title":"Stochastic games and applications","author":"Thuijsman F.","key":"e_1_2_1_48_1","unstructured":"F. Thuijsman . 2003. The big match and the Paris match . In Stochastic games and applications . Springer , 195--204. F. Thuijsman. 2003. The big match and the Paris match. In Stochastic games and applications. Springer, 195--204."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01720283"},{"key":"e_1_2_1_50_1","unstructured":"O. J. Vrieze. 1987. Stochastic Games with Finite State and Action Spaces. Centrum voor Wiskunde en Informatica. https:\/\/books.google.fr\/books?id=59tbPwAACAAJ  O. J. Vrieze. 1987. Stochastic Games with Finite State and Action Spaces. Centrum voor Wiskunde en Informatica. https:\/\/books.google.fr\/books?id=59tbPwAACAAJ"}],"container-title":["ACM SIGLOG News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583660.3583666","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583660.3583666","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:54Z","timestamp":1750178274000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583660.3583666"}},"subtitle":["Can the King Cautiously Eliminate Robin Hood?"],"short-title":[],"issued":{"date-parts":[[2022,10]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["10.1145\/3583660.3583666"],"URL":"https:\/\/doi.org\/10.1145\/3583660.3583666","relation":{},"ISSN":["2372-3491"],"issn-type":[{"type":"electronic","value":"2372-3491"}],"subject":[],"published":{"date-parts":[[2022,10]]},"assertion":[{"value":"2023-02-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}