{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:19:57Z","timestamp":1760080797256,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031308284"},{"type":"electronic","value":"9783031308291"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T00:00:00Z","timestamp":1682035200000},"content-version":"vor","delay-in-days":110,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate concurrent two-player win\/lose stochastic games on finite graphs with prefix-independent objectives. We characterize subgame optimal strategies and use this characterization to show various memory transfer results: 1) For a given (prefix-independent) objective, if every game that has a subgame<jats:italic>almost-surely winning<\/jats:italic>strategy also has a positional one, then every game that has a subgame<jats:italic>optimal<\/jats:italic>strategy also has a positional one; 2) Assume that the (prefix-independent) objective has a neutral color. If every<jats:italic>turn-based<\/jats:italic>game that has a subgame almost-surely winning strategy also has a positional one, then every game that has a<jats:italic>finite-choice<\/jats:italic>(notion to be defined) subgame optimal strategy also has a positional one.<\/jats:p><jats:p>We collect or design examples to show that our results are tight in several ways. We also apply our results to B\u00fcchi, co-B\u00fcchi, parity, mean-payoff objectives, thus yielding simpler statements.<\/jats:p>","DOI":"10.1007\/978-3-031-30829-1_26","type":"book-chapter","created":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T19:56:19Z","timestamp":1682020579000},"page":"541-560","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Subgame Optimal Strategies in Finite Concurrent Games with Prefix-Independent Objectives"],"prefix":"10.1007","author":[{"given":"Benjamin","family":"Bordais","sequence":"first","affiliation":[]},{"given":"Patricia","family":"Bouyer","sequence":"additional","affiliation":[]},{"given":"St\u00e9phane Le","family":"Roux","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,21]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Roderick Bloem, Krishnendu Chatterjee, and Barbara Jobstmann. Handbook of Model Checking, chapter Graph games and reactive synthesis, pages 921\u2013962. Springer, 2018.","DOI":"10.1007\/978-3-319-10575-8_27"},{"key":"26_CR2","unstructured":"Benjamin Bordais, Patricia Bouyer, and St\u00e9phane\u00a0Le Roux. From local to global determinacy in concurrent graph games. In Mikolaj Bojanczyk and Chandra Chekuri, editors, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021, December 15-17, 2021, Virtual Conference, volume 213 of LIPIcs, pages 41:1\u201341:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2021."},{"key":"26_CR3","unstructured":"Benjamin Bordais, Patricia Bouyer, and St\u00e9phane\u00a0Le Roux. Optimal strategies in concurrent reachability games. In Florin Manea and Alex Simpson, editors, 30th EACSL Annual Conference on Computer Science Logic, CSL 2022, February 14-19, 2022, G\u00f6ttingen, Germany (Virtual Conference), volume 216 of LIPIcs, pages 7:1\u20137:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2022."},{"key":"26_CR4","unstructured":"Benjamin Bordais, Patricia Bouyer, and St\u00e9phane\u00a0Le Roux. Playing (almost-)optimally in concurrent b\u00fcchi and co-b\u00fcchi games. CoRR, abs\/2203.06966, 2022."},{"key":"26_CR5","unstructured":"Benjamin Bordais, Patricia Bouyer, and St\u00e9phane\u00a0Le Roux. Sub-game optimal strategies in concurrent games with prefix-independent objectives. CoRR, abs\/2301.10697, 2023."},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Krishnendu Chatterjee. Concurrent games with tail objectives. Theor. Comput. Sci., 388(1-3):181\u2013198, 2007.","DOI":"10.1016\/j.tcs.2007.07.047"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Krishnendu Chatterjee, Luca de\u00a0Alfaro, and Thomas\u00a0A. Henzinger. Trading memory for randomness. In 1st International Conference on Quantitative Evaluation of Systems (QEST 2004), 27-30 September 2004, Enschede, The Netherlands, pages 206\u2013217. IEEE Computer Society, 2004.","DOI":"10.1109\/QEST.2004.1348035"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Krishnendu Chatterjee, Luca de\u00a0Alfaro, and Thomas\u00a0A. Henzinger. The complexity of quantitative concurrent parity games. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 678\u2013687. ACM Press, 2006.","DOI":"10.1145\/1109557.1109631"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Krishnendu Chatterjee, Laurent Doyen, Hugo Gimbert, and Thomas\u00a0A. Henzinger. Randomness for free. Inf. Comput., 245:3\u201316, 2015.","DOI":"10.1016\/j.ic.2015.06.003"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Krishnendu Chatterjee and Rasmus Ibsen-Jensen. Qualitative analysis of concurrent mean-payoff games. Inf. Comput., 242:2\u201324, 2015.","DOI":"10.1016\/j.ic.2015.03.009"},{"key":"26_CR11","unstructured":"Krishnendu Chatterjee, Marcin Jurdzinski, and Thomas\u00a0A. Henzinger. Quantitative stochastic parity games. In J.\u00a0Ian Munro, editor, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pages 121\u2013130. SIAM, 2004."},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Luca de\u00a0Alfaro and Thomas\u00a0A. Henzinger. Concurrent omega-regular games. In 15th Annual IEEE Symposium on Logic in Computer Science, Santa Barbara, California, USA, June 26-29, 2000, pages 141\u2013154. IEEE Computer Society, 2000.","DOI":"10.1109\/LICS.2000.855763"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Hugh Everett. Recursive games. Annals of Mathematics Studies \u2013 Contributions to the Theory of Games, 3:67\u201378, 1957.","DOI":"10.1515\/9781400882151-004"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Hugo Gimbert and Florian Horn. Solving simple stochastic tail games. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 847\u2013862. SIAM, 2010.","DOI":"10.1137\/1.9781611973075.69"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Marta Kwiatkowska, Gethin Norman, Dave Parker, and Gabriel Santos. Automatic verification of concurrent stochastic systems. Formal Methods in System Design, 58:188\u2013250, 2021.","DOI":"10.1007\/s10703-020-00356-y"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Thomas\u00a0M Liggett and Steven\u00a0A Lippman. Stochastic games with perfect information and time average payoff. Siam Review, 11(4):604\u2013607, 1969.","DOI":"10.1137\/1011093"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Donald\u00a0A. Martin. The determinacy of blackwell games. The Journal of Symbolic Logic, 63(4):1565\u20131581, 1998.","DOI":"10.2307\/2586667"},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"Lloyd\u00a0S Shapley and RN\u00a0Snow. Basic solutions of discrete games. Contributions to the Theory of Games, 1(24):27\u201327, 1950.","DOI":"10.1515\/9781400881727-004"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Wolfgang Thomas. Infinite games and verification. In Proc. 14th International Conference on Computer Aided Verification (CAV\u201902), volume 2404 of Lecture Notes in Computer Science, pages 58\u201364. Springer, 2002. Invited Tutorial.","DOI":"10.1007\/3-540-45657-0_5"},{"key":"26_CR20","unstructured":"John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton Univ. Press, Princeton, 1944."}],"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-30829-1_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,18]],"date-time":"2024-10-18T22:42:38Z","timestamp":1729291358000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30829-1_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031308284","9783031308291"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30829-1_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"21 April 2023","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":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 April 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 April 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2023\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"85","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}