Strategy Complexity of Büchi and Transience Objectives in Concurrent Stochastic Games

References

• [1] Abdou J, Pnevmatikos N, Scarsini M, Venel X (2022) Decomposition of games: Some strategic considerations. Math. Oper. Res. 47(1):176–208.Link, Google Scholar
• [2] Altman E, Avrachenkov K, Marquez R, Miller GB (2005) Zero-sum constrained stochastic games with independent state processes. Math. Methods Oper. Res. 62(3):375–386.Crossref, Google Scholar
• [3] Altman E, Avrachenkov K, Bonneau N, Debbah M, El-Azouzi R, Menasche DM (2007) Constrained stochastic games in wireless networks. IEEE Global Commun. Conf. GLOBECOM 2007 (IEEE, Piscataway, NJ), 315–320.Google Scholar
• [4] Bacharach M (2019) Economics and the Theory of Games (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• [5] Billingsley P (1995) Probability and Measure. 3rd ed. (Wiley, New York).Google Scholar
• [6] Bordais B, Bouyer P, Le Roux S (2022) Playing (almost-)optimally in concurrent Büchi and co-Büchi games. Dawar A, Guruswami V, eds. 42nd IARCS Annu. Conf. Foundations Software Tech. Theor. Comput. Sci. FSTTCS 2022, Leibniz International Proceedings in Informatics, vol. 250 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 33:1–33:18.Google Scholar
• [7] Bordais B, Bouyer P, Roux SL (2022) Optimal strategies in concurrent reachability games. Manea F, Simpson A, eds. 30th EACSL Annu. Conf. Comput. Sci. Logic CSL 2022, Leibniz International Proceedings in Informatics, vol. 216 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 7:1–7:17.Google Scholar
• [8] Bouyer P, Markey N, Randour M, Sangnier A, Stan D (2016) Reachability in networks of register protocols under stochastic schedulers. Internat. Colloquium Automata Languages Program. ICALP, Leibniz International Proceedings in Informatics, vol. 55 (Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 106:1–106:14.Google Scholar
• [9] Condon A (1992) The complexity of stochastic games. Inform. Comput. 96(2):203–224.Crossref, Google Scholar
• [10] de Alfaro L, Henzinger T (2000) Concurrent omega-regular games. Proc. 15th Annu. IEEE Sympos. Logic Comput. Sci. LICS 2000 (IEEE, Piscataway, NJ), 141–154.Google Scholar
• [11] de Alfaro L, Henzinger TA (2001) Interface automata. Internat. Sympos. Foundations Software Engrg. (Association for Computing Machinery, New York), 109–120.Google Scholar
• [12] de Alfaro L, Henzinger TA, Kupferman O (1998) Concurrent reachability games. 39th Annu. Sympos. Foundations Comput. Sci. FOCS ‘98 (IEEE Computer Society, Piscataway, NJ), 564–575.Google Scholar
• [13] Everett H (1957) Recursive games. Kuhn HW, ed. Contributions to the Theory of Games III, Annals of Mathematics Studies, vol. 39 (Princeton University Press, Princeton, NJ), 47–78.Google Scholar
• [14] Flesch J, Predtetchinski A, Sudderth W (2020) Positive zero-sum stochastic games with countable state and action spaces. Appl. Math. Optim. 82:499–516.Crossref, Google Scholar
• [15] Gillette D (1958) Stochastic games with zero stop probabilities. Dresher M, Tucker AW, and Wolfe P, eds. Games with Perfect Information II, Annals of Mathematics Studies, vol. 39 (Princeton University Press, Princeton, NJ), 179–188.Crossref, Google Scholar
• [16] Grädel E, Thomas W, Wilke T, eds. (2002) Automata, Logics, and Infinite Games, Lecture Notes in Computer Science, vol. 2500 (Springer, Berlin, Heidelberg).Google Scholar
• [17] Jaśkiewicz A, Nowak AS (2011) Stochastic games with unbounded payoffs: Applications to robust control in economics. Dynam. Games Appl. 1(2):253–279.Crossref, Google Scholar
• [18] Kiefer S, Mayr R, Shirmohammadi M, Totzke P (2019) Büchi objectives countable MDPs. Internat. Colloquium Automata Languages Program. ICALP, Leibniz International Proceedings in Informatics, vol. 132 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 119:1–119:14.Google Scholar
• [19] Kiefer S, Mayr R, Shirmohammadi M, Totzke P (2020) Strategy complexity of parity objectives in countable MDPs. Internat. Conf. Concurrency Theory CONCUR (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 39:1–39:17.Google Scholar
• [20] Kiefer S, Mayr R, Shirmohammadi M, Totzke P (2021) Transience in countable MDPs. Internat. Conf. Concurrency Theory CONCUR, Leibniz International Proceedings in Informatics, vol. 203 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 11:1–11:15.Google Scholar
• [21] Kiefer S, Mayr R, Shirmohammadi M, Totzke P (2025) Strategy complexity of reachability in countable stochastic 2-player games. Dynam. Games Appl. 15(3):980–1036.Crossref, Google Scholar
• [22] Kiefer S, Mayr R, Shirmohammadi M, Totzke P (2026) No good Markov strategies for Büchi objectives in countable MDPs. Ann. Oper. Res. 361:711–726.Crossref, Google Scholar
• [23] Kiefer S, Mayr R, Shirmohammadi M, Wojtczak D (2017) Parity objectives in countable MDPs. ACM/IEEE Sympos. Logic Comput. Sci. LICS (IEEE, Piscataway, NJ), 1–11.Google Scholar
• [24] Kumar PR, Shiau TH (1981) Existence of value and randomized strategies in zero-sum discrete-time stochastic dynamic games. SIAM J. Control Optim. 19(5):617–634.Crossref, Google Scholar
• [25] Maitra A, Sudderth W (1998) Finitely additive stochastic games with Borel measurable payoffs. Internat. J. Game Theory 27(2):257–267.Crossref, Google Scholar
• [26] Maitra AP, Sudderth WD (1996) Discrete Gambling and Stochastic Games (Springer-Verlag, New York).Crossref, Google Scholar
• [27] Martin DA (1998) The determinacy of Blackwell games. J. Symbolic Logic 63(4):1565–1581.Crossref, Google Scholar
• [28] Mertens JF, Neyman A, Rosenberg D (2009) Absorbing games with compact action spaces. Math. Oper. Res. 34(2):257–262.Link, Google Scholar
• [29] Neveu J (1975) Discrete-Parameter Martingales (North-Holland Publishing Company, Amsterdam).Google Scholar
• [30] Neyman A, Sorin S (2003) Stochastic Games and Applications (Springer, Dordrecht, Netherlands).Crossref, Google Scholar
• [31] Nowak A, Szajowski K (2005) Advances in Dynamic Games: Applications to Economics, Finance, Optimization, and Stochastic Control (Birkhäuser, Boston).Crossref, Google Scholar
• [32] Ornstein D (1969) On the existence of stationary optimal strategies. Proc. Amer. Math. Soc. 20(2):563–569.Crossref, Google Scholar
• [33] Osmani L, Lisser A, Singh VV (2026) Zero-sum discounted stochastic games with random rewards. Ann. Oper. Res. 358(3):1453–1484.Crossref, Google Scholar
• [34] Ponssard JP, Sorin S (1982) Optimal behavioral strategies in 0-sum games with almost perfect information. Math. Oper. Res. 7(1):14–31.Link, Google Scholar
• [35] Raghavan TES, Ferguson T, Parthasarathy T, Vrieze O (2012) Stochastic Games and Related Topics: In Honor of Professor LS Shapley, vol. 7 (Springer Science & Business Media, Dordrecht, Netherlands).Google Scholar
• [36] Resnick SI (2014) A Probability Path, Modern Birkhäuser Classics. 1st ed. (Birkhäuser, Boston).Crossref, Google Scholar
• [37] Secchi P (1997) Stationary strategies for recursive games. Math. Oper. Res. 22(2):494–512.Link, Google Scholar
• [38] Secchi P (1998) On the existence of good stationary strategies for nonleavable stochastic games. Internat. J. Game Theory 27:61–81.Crossref, Google Scholar
• [39] Shapley LS (1953) Stochastic games. Proc. Natl. Acad. Sci. USA 39(10):1095–1100.Crossref, Google Scholar
• [40] Solan E, Vieille N (2001) Quitting games. Math. Oper. Res. 26(2):265–285.Link, Google Scholar
• [41] Solan E, Vieille N (2015) Stochastic games. Proc. Natl. Acad. Sci. USA 112(45):13743–13746.Crossref, Google Scholar
• [42] Sorin S (1992) Repeated games with complete information. Aumann R, Hart S, eds. Handbook of Game Theory with Economic Applications, vol. 1 (Elsevier, Amsterdam), 71–107.Crossref, Google Scholar
• [43] Svoreňová M, Kwiatkowska M (2016) Quantitative verification and strategy synthesis for stochastic games. Eur. J. Control 30:15–30.Crossref, Google Scholar
• [44] Thuijsman F (1992) Optimality and Equilibria in Stochastic Games, CWI Tract – Centrum voor Wiskunde en Informatica, vol. 82 (Centrum voor Wiskunde en Informatica, Amsterdam).Google Scholar
• [45] Zielonka W (2004) Perfect-information stochastic parity games. Walukiewicz I, ed. Foundations of Software Science and Computation Structures, Lecture Notes in Computer Science, vol. 2987 (Springer, Berlin, Heidelberg), 499–513.Crossref, Google Scholar