{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T11:17:21Z","timestamp":1782991041852,"version":"3.54.5"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032227294","type":"print"},{"value":"9783032227300","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-22730-0_3","type":"book-chapter","created":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T16:24:35Z","timestamp":1776270275000},"page":"43-64","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Games with Randomised Control"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-4476-489X","authenticated-orcid":false,"given":"Sarvin","family":"Bahmani","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4783-0389","authenticated-orcid":false,"given":"Rasmus","family":"Ibsen-Jensen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7233-2018","authenticated-orcid":false,"given":"Soumyajit","family":"Paul","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9093-9518","authenticated-orcid":false,"given":"Sven","family":"Schewe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1784-2346","authenticated-orcid":false,"given":"Friedrich","family":"Slivovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9265-3011","authenticated-orcid":false,"given":"Qiyi","family":"Tang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5560-0546","authenticated-orcid":false,"given":"Dominik","family":"Wojtczak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5922-8750","authenticated-orcid":false,"given":"Shufang","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,4,15]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","unstructured":"de\u00a0Alfaro, L., Henzinger, T.A., Majumdar, R.: From verification to control: Dynamic programs for omega-regular objectives. In: 16th Annual IEEE Symposium on Logic in Computer Science, Boston, Massachusetts, USA, June 16-19, 2001, Proceedings. pp. 279\u2013290. IEEE Computer Society (2001). https:\/\/doi.org\/10.1109\/LICS.2001.932504","DOI":"10.1109\/LICS.2001.932504"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. Journal of the ACM (JACM) 49(5), 672\u2013713 (2002)","DOI":"10.1145\/585265.585270"},{"key":"3_CR3","unstructured":"Austin, P., Dell\u2019Erba, D., Totzke, P.: Game graph gym. https:\/\/github.com\/gamegraphgym\/ggg, commit: 5d31ac68e36cd781bfa00b9672ea0861872c45cf, Accessed: 2025-10-02"},{"key":"3_CR4","doi-asserted-by":"publisher","unstructured":"Avni, G., Ghorpade, P., Guha, S.: A game of pawns. Log. Methods Comput. Sci. 21(2) (2025). https:\/\/doi.org\/10.46298\/LMCS-21(2:3)2025","DOI":"10.46298\/LMCS-21(2:3)2025"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Avni, G., Henzinger, T.A., Chonev, V.: Infinite-duration bidding games. Journal of the ACM (JACM) 66(4), 1\u201329 (2019)","DOI":"10.1145\/3340295"},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"Avni, G., Henzinger, T.A., Ibsen-Jensen, R.: Infinite-duration poorman-bidding games. In: Web and Internet Economics - 14th International Conference, WINE 2018, Oxford, UK, December 15-17, 2018, Proceedings. pp. 21\u201336 (2018)","DOI":"10.1007\/978-3-030-04612-5_2"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Bahmani, S., Ibsen-Jensen, R., Paul, S., Schewe, S., Slivovsky, F., Tang, Q., Wojtczak, D., Zhu, S.: The complexity of games with randomised control (2026), https:\/\/arxiv.org\/abs\/2601.07775","DOI":"10.1007\/978-3-032-22730-0_3"},{"key":"3_CR8","doi-asserted-by":"publisher","unstructured":"Bahmani, S., Ibsen-Jensen, R., Paul, S., Schewe, S., Slivovsky, F., Tang, Q., Wojtczak, D., Zhu, S.: Experiments for random arena games (Jan 2026). https:\/\/doi.org\/10.5281\/zenodo.18166538","DOI":"10.5281\/zenodo.18166538"},{"key":"3_CR9","doi-asserted-by":"publisher","unstructured":"Benerecetti, M., Dell\u2019Erba, D., Mogavero, F.: Solving parity games via priority promotion. Formal Methods Syst. Des. 52(2), 193\u2013226 (2018). https:\/\/doi.org\/10.1007\/S10703-018-0315-1","DOI":"10.1007\/S10703-018-0315-1"},{"key":"3_CR10","doi-asserted-by":"publisher","unstructured":"Bloem, R., Chatterjee, K., Jobstmann, B.: Graph Games and Reactive Synthesis, pp. 921\u2013962. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-10575-8_27","DOI":"10.1007\/978-3-319-10575-8_27"},{"key":"3_CR11","doi-asserted-by":"publisher","unstructured":"Bouyer, P., Fahrenberg, U., Larsen, K.G., Markey, N., Srba, J.: Infinite runs in weighted timed automata with energy constraints. In: Cassez, F., Jard, C. (eds.) Formal Modeling and Analysis of Timed Systems, 6th International Conference, FORMATS 2008, Saint Malo, France, September 15-17, 2008. Proceedings. Lecture Notes in Computer Science, vol.\u00a05215, pp. 33\u201347. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-540-85778-5_4","DOI":"10.1007\/978-3-540-85778-5_4"},{"key":"3_CR12","doi-asserted-by":"publisher","unstructured":"Brim, L., Chaloupka, J., Doyen, L., Gentilini, R., Raskin, J.: Faster algorithms for mean-payoff games. Formal Methods Syst. Des. 38(2), 97\u2013118 (2011). https:\/\/doi.org\/10.1007\/S10703-010-0105-X","DOI":"10.1007\/S10703-010-0105-X"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Celis, L.E., Devanur, N.R., Peres, Y.: Local dynamics in bargaining networks via random-turn games. In: Proceedings of the 6th International Conference on Internet and Network Economics. p. 133\u2013144. WINE\u201910, Springer-Verlag, Berlin, Heidelberg (2010)","DOI":"10.1007\/978-3-642-17572-5_11"},{"key":"3_CR14","doi-asserted-by":"publisher","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM 28(1), 114\u2013133 (Jan 1981). https:\/\/doi.org\/10.1145\/322234.322243","DOI":"10.1145\/322234.322243"},{"key":"3_CR15","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., Henzinger, T.A.: Reduction of stochastic parity to stochastic mean-payoff games. Inf. Process. Lett. 106(1), \u00a01\u20137 (2008). https:\/\/doi.org\/10.1016\/J.IPL.2007.08.035","DOI":"10.1016\/J.IPL.2007.08.035"},{"key":"3_CR16","unstructured":"Chatterjee, K., Jurdzinski, M., Henzinger, T.A.: Quantitative stochastic parity games. In: Munro, J.I. (ed.) Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004. pp. 121\u2013130. SIAM (2004), http:\/\/dl.acm.org\/citation.cfm?id=982792.982808"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Condon, A.: The complexity of stochastic games. Information and Computation pp. 203\u2013224 (1992)","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"3_CR18","doi-asserted-by":"publisher","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. International Journal of Game Theory 8, 109\u2013113 (1979). https:\/\/doi.org\/10.1007\/BF01768705","DOI":"10.1007\/BF01768705"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy (extended abstract). In: FOCS. pp. 368\u2013377. IEEE Computer Society (1991), http:\/\/dblp.uni-trier.de\/db\/conf\/focs\/focs91.html#EmersonJ91","DOI":"10.1109\/SFCS.1991.185392"},{"key":"3_CR20","doi-asserted-by":"publisher","unstructured":"Fijalkow, N., Aiswarya, C., Avni, G., Bertrand, N., Bouyer, P., Brenguier, R., Carayol, A., Casares, A., Fearnley, J., Gastin, P., Gimbert, H., Henzinger, T.A., Horn, F., Ibsen-Jensen, R., Markey, N., Monmege, B., Novotn\u00fd, P., Ohlmann, P., Randour, M., Sankur, O., Schmitz, S., Serre, O., Skomra, M., Sznajder, N., Vandenhove, P.: Games on graphs: From logic and automata to algorithms (2025). https:\/\/doi.org\/10.48550\/arXiv.2305.10546","DOI":"10.48550\/arXiv.2305.10546"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Goldschlager, L.M.: The monotone and planar circuit value problems are log space complete for P. SIGACT News 9(2), 25\u201329 (Summer 1977)","DOI":"10.1145\/1008354.1008356"},{"key":"3_CR22","doi-asserted-by":"publisher","unstructured":"Gurvich, V., Karzanov, A., Khachivan, L.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Computational Mathematics and Mathematical Physics 28(5), 85\u201391 (1988). https:\/\/doi.org\/10.1016\/0041-5553(88)90012-2","DOI":"10.1016\/0041-5553(88)90012-2"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. Journal of the American statistical association 58(301), 13\u201330 (1963)","DOI":"10.1080\/01621459.1963.10500830"},{"key":"3_CR24","doi-asserted-by":"publisher","unstructured":"Jurdzinski, M.: Deciding the winner in parity games is in UP $$\\cap $$ co-UP. Inf. Process. Lett. 68(3), 119\u2013124 (1998). https:\/\/doi.org\/10.1016\/S0020-0190(98)00150-1","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Kupferman, O., Vardi, M.Y.: Module checking revisited. In: International Conference on Computer Aided Verification. pp. 36\u201347. Springer (1997)","DOI":"10.1007\/3-540-63166-6_7"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Lazarus, A.J., Loeb, D.E., Propp, J.G., Stromquist, W.R., Ullman, D.H.: Combinatorial games under auction play. Games and Economic Behavior 27(2), 229\u2013264 (1999)","DOI":"10.1006\/game.1998.0676"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Lazarus, A.J., Loeb, D.E., Propp, J.G., Ullman, D.: Richman games. Games of no chance 29, 439\u2013449 (1996)","DOI":"10.1017\/9781009701839.037"},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Lehtinen, K., Parys, P., Schewe, S., Wojtczak, D.: A recursive approach to solving parity games in quasipolynomial time. Logical Methods in Computer Science 18 (2022)","DOI":"10.46298\/lmcs-18(1:8)2022"},{"key":"3_CR29","unstructured":"Mostowski, A.: Games with Forbidden Positions. Preprint - Uniwersytet Gda\u0144ski. Instytut Matematyki, UG (1991), https:\/\/books.google.co.uk\/books?id=clvwtgAACAAJ"},{"key":"3_CR30","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading, MA (1994)"},{"key":"3_CR31","doi-asserted-by":"publisher","unstructured":"Peres, Y., Schramm, O., Sheffield, S., Wilson, D.B.: Tug-of-war and the infinity laplacian. Journal of the American Mathematical Society 22(1), 167\u2013210 (2009). https:\/\/doi.org\/10.1090\/S0894-0347-08-00606-1","DOI":"10.1090\/S0894-0347-08-00606-1"},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"Peres, Y., Schramm, O., Sheffield, S., Wilson, D.B.: Random-turn hex and other selection games. The American Mathematical Monthly 114, 373 \u2013 387 (2005), https:\/\/api.semanticscholar.org\/CorpusID:15583858","DOI":"10.1080\/00029890.2007.11920428"},{"key":"3_CR33","doi-asserted-by":"publisher","unstructured":"Pnueli, A., Rosner, R.: On the synthesis of a reactive module. In: Symposium on Principles of Programming Languages (POPL 1989). p. 179\u2013190. Association for Computing Machinery (1989). https:\/\/doi.org\/10.1145\/75277.75293","DOI":"10.1145\/75277.75293"},{"key":"3_CR34","doi-asserted-by":"publisher","unstructured":"Provan, J.S.: The complexity of reliability computations in planar and acyclic graphs. SIAM Journal on Computing 15(3), 694\u2013702 (1986). https:\/\/doi.org\/10.1137\/0215050","DOI":"10.1137\/0215050"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing 12(4), 777\u2013788 (1983)","DOI":"10.1137\/0212053"},{"key":"3_CR36","doi-asserted-by":"publisher","unstructured":"Rubinstein, R.Y., Kroese, D.P.: Simulation and the Monte Carlo Method. Wiley Series in Probability and Statistics, Wiley, 2 edn. (2007).https:\/\/doi.org\/10.1002\/9780470230381","DOI":"10.1002\/9780470230381"},{"key":"3_CR37","unstructured":"Totzke, P.: Egsolver. https:\/\/github.com\/pazz\/egsolver, commit:4f8c500f892c10073a8e3b52cf6700ddbf2deeda, Accessed: 2025-10-10"},{"key":"3_CR38","doi-asserted-by":"publisher","unstructured":"Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theor. Comput. Sci. 158(1&2), 343\u2013359 (1996). https:\/\/doi.org\/10.1016\/0304-3975(95)00188-3","DOI":"10.1016\/0304-3975(95)00188-3"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-22730-0_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T23:48:05Z","timestamp":1782949685000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-22730-0_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032227294","9783032227300"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-22730-0_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"15 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Turin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2026\/conferences\/fossacs\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}