{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T08:14:21Z","timestamp":1783671261287,"version":"3.55.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031572272","type":"print"},{"value":"9783031572289","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T00:00:00Z","timestamp":1712275200000},"content-version":"vor","delay-in-days":95,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Stochastic two-player games model systems with an environment that is both adversarial and stochastic. The environment is modeled by a player (\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\text {Player}~{2}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>Player<\/mml:mtext>\n                            <mml:mspace\/>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    ) who tries to prevent the system (\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\text {Player}~{1}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>Player<\/mml:mtext>\n                            <mml:mspace\/>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    ) from achieving its objective. We consider finitary versions of the traditional mean-payoff objective, replacing the long-run average of the payoffs by payoff average computed over a finite sliding window. Two variants have been considered: in one variant, the maximum window length is fixed and given, while in the other, it is not fixed but is required to be bounded. For both variants, we present complexity bounds and algorithmic solutions for computing strategies for\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\text {Player}~{1}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>Player<\/mml:mtext>\n                            <mml:mspace\/>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    to ensure that the objective is satisfied with positive probability, with probability\u00a01, or with probability at least\u00a0\n                    <jats:italic>p<\/jats:italic>\n                    , regardless of the strategy of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\text {Player}~{2}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>Player<\/mml:mtext>\n                            <mml:mspace\/>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . The solution crucially relies on a reduction to the special case of non-stochastic two-player games. We give a general characterization of prefix-independent objectives for which this reduction holds. The memory requirement for both players in stochastic games is also the same as in non-stochastic games by our reduction. Moreover, for non-stochastic games, we improve upon the upper bound for the memory requirement of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\text {Player}~{1}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>Player<\/mml:mtext>\n                            <mml:mspace\/>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and upon the lower bound for the memory requirement of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\text {Player}~{2}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>Player<\/mml:mtext>\n                            <mml:mspace\/>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>","DOI":"10.1007\/978-3-031-57228-9_3","type":"book-chapter","created":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T04:03:04Z","timestamp":1712203384000},"page":"34-54","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Stochastic Window Mean-Payoff Games"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3714-6145","authenticated-orcid":false,"given":"Laurent","family":"Doyen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8012-780X","authenticated-orcid":false,"given":"Pranshu","family":"Gaba","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9814-6651","authenticated-orcid":false,"given":"Shibashis","family":"Guha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,4,5]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Alur, R., Henzinger, T.A.: Finitary fairness. In: LICS. pp. 52\u201361. IEEE Computer Society (1994)","DOI":"10.1109\/LICS.1994.316087"},{"key":"3_CR2","unstructured":"Baier, C., Katoen, J.: Principles of model checking. MIT Press (2008)"},{"key":"3_CR3","unstructured":"Bordais, B., Guha, S., Raskin, J.F.: Expected window mean-payoff. In: FSTTCS. LIPIcs, vol.\u00a0150, pp. 32:1\u201332:15 (2019)"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Brihaye, T., Delgrange, F., Oualhadj, Y., Randour, M.: Life is Random, Time is Not: Markov Decision Processes with Window Objectives. Logical Methods in Computer Science Volume 16, Issue 4 (Dec 2020)","DOI":"10.23638\/LMCS-16(4:13)2020"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Bruy\u00e8re, V., Hautem, Q., Randour, M.: Window parity games: an alternative approach toward parity games with time bounds. In: GandALF. EPTCS, vol.\u00a0226, pp. 135\u2013148 (2016)","DOI":"10.4204\/EPTCS.226.10"},{"key":"3_CR6","unstructured":"Bruy\u00e8re, V., Hautem, Q., Raskin, J.F.: On the complexity of heterogeneous multidimensional games. In: CONCUR. LIPIcs, vol.\u00a059, pp. 11:1\u201311:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Chatterjee, K.: Concurrent games with tail objectives. Theoretical Computer Science 388(1), 181\u2013198 (2007)","DOI":"10.1016\/j.tcs.2007.07.047"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Doyen, L., Randour, M., Raskin, J.F.: Looking at mean-payoff and total-payoff through windows. Information and Computation 242, 25\u201352 (2015)","DOI":"10.1016\/j.ic.2015.03.010"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.A.: Finitary winning in $$\\omega $$-regular games. In: TACAS. pp. 257\u2013271. LNCS 3920, Springer (2006)","DOI":"10.1007\/11691372_17"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.A.: Value iteration. In: 25 Years of Model Checking - History, Achievements, Perspectives. pp. 107\u2013138. LNCS 5000, Springer (2008)","DOI":"10.1007\/978-3-540-69850-0_7"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.A.: A survey of stochastic $$\\omega $$-regular games. Journal of Computer and System Sciences 78(2), 394\u2013413 (2012)","DOI":"10.1016\/j.jcss.2011.05.002"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.A., Horn, F.: Finitary winning in omega-regular games. ACM Trans. Comput. Log. 11(1), 1:1\u20131:27 (2009)","DOI":"10.1145\/1614431.1614432"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.A., Horn, F.: Stochastic games with finitary objectives. In: MFCS. pp. 34\u201354. Springer Berlin Heidelberg (2009)","DOI":"10.1007\/978-3-642-03816-7_4"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Condon, A.: The complexity of stochastic games. Information and Computation 96(2), 203\u2013224 (1992)","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"3_CR15","unstructured":"Doyen, L., Gaba, P., Guha, S.: Stochastic window mean-payoff games. CoRR abs\/2304.11563 (2023), https:\/\/arxiv.org\/abs\/2304.11563"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Int. Journal of Game Theory 8(2), 109\u2013113 (1979)","DOI":"10.1007\/BF01768705"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer (1997)","DOI":"10.1007\/978-1-4612-4054-9"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. LNCS 2500, Springer (2002)","DOI":"10.1007\/3-540-36387-4"},{"key":"3_CR19","unstructured":"Hautem, Q.: The Complexity of Combining Objectives in Two-Player Games. Ph.D. thesis, Universit\u00e9 de Mons (2018)"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Horn, F.: Faster algorithms for finitary games. In: TACAS. Lecture Notes in Computer Science, vol.\u00a04424, pp. 472\u2013484. Springer (2007)","DOI":"10.1007\/978-3-540-71209-1_36"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Horn, F., Thomas, W., Wallmeier, N., Zimmermann, M.: Optimal strategy synthesis for request-response games. RAIRO Theor. Informatics Appl. 49(3), 179\u2013203 (2015)","DOI":"10.1051\/ita\/2015005"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Jurdzinski, M.: Deciding the winner in parity games is in UP $$\\cap $$ co-UP. Inf. Process. Lett. 68(3), 119\u2013124 (1998)","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Kupferman, O., Piterman, N., Vardi, M.Y.: From liveness to promptness. Formal Methods Syst. Des. 34(2), 83\u2013103 (2009)","DOI":"10.1007\/s10703-009-0067-z"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Martin, D.A.: The determinacy of blackwell games. The Journal of Symbolic Logic 63(4), 1565\u20131581 (1998), http:\/\/www.jstor.org\/stable\/2586667","DOI":"10.2307\/2586667"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A low and a high hierarchy within NP. Journal of Computer and System Sciences 27(1), 14\u201328 (1983)","DOI":"10.1016\/0022-0000(83)90027-2"},{"key":"3_CR26","unstructured":"Weinert, A., Zimmermann, M.: Easy to win, hard to master: Optimal strategies in parity games with costs. In: CSL. LIPIcs, vol.\u00a062, pp. 31:1\u201331:17 (2016)"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theor. Comput. Sci. 158(1 &2), 343\u2013359 (1996)","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-031-57228-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T07:28:50Z","timestamp":1783668530000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-57228-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031572272","9783031572289"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-57228-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"5 April 2024","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":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 April 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2024\/conferences\/fossacs\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}