{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:46:16Z","timestamp":1762299976044,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,1,17]],"date-time":"2022-01-17T00:00:00Z","timestamp":1642377600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>For decades, two-player (antagonistic) games on graphs have been a framework\nof choice for many important problems in theoretical computer science. A\nnotorious one is controller synthesis, which can be rephrased through the\ngame-theoretic metaphor as the quest for a winning strategy of the system in a\ngame against its antagonistic environment. Depending on the specification,\noptimal strategies might be simple or quite complex, for example having to use\n(possibly infinite) memory. Hence, research strives to understand which\nsettings allow for simple strategies.\n  In 2005, Gimbert and Zielonka provided a complete characterization of\npreference relations (a formal framework to model specifications and game\nobjectives) that admit memoryless optimal strategies for both players. In the\nlast fifteen years however, practical applications have driven the community\ntoward games with complex or multiple objectives, where memory -- finite or\ninfinite -- is almost always required. Despite much effort, the exact frontiers\nof the class of preference relations that admit finite-memory optimal\nstrategies still elude us.\n  In this work, we establish a complete characterization of preference\nrelations that admit optimal strategies using arena-independent finite memory,\ngeneralizing the work of Gimbert and Zielonka to the finite-memory case. We\nalso prove an equivalent to their celebrated corollary of great practical\ninterest: if both players have optimal (arena-independent-)finite-memory\nstrategies in all one-player games, then it is also the case in all two-player\ngames. Finally, we pinpoint the boundaries of our results with regard to the\nliterature: our work completely covers the case of arena-independent memory\n(e.g., multiple parity objectives, lower- and upper-bounded energy objectives),\nand paves the way to the arena-dependent case (e.g., multiple lower-bounded\nenergy objectives).<\/jats:p>","DOI":"10.46298\/lmcs-18(1:11)2022","type":"journal-article","created":{"date-parts":[[2022,1,19]],"date-time":"2022-01-19T20:54:22Z","timestamp":1642625662000},"source":"Crossref","is-referenced-by-count":4,"title":["Games Where You Can Play Optimally with Arena-Independent Finite Memory"],"prefix":"10.46298","volume":"Volume 18, Issue 1","author":[{"given":"Patricia","family":"Bouyer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane Le","family":"Roux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Youssouf","family":"Oualhadj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mickael","family":"Randour","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5834-1068","authenticated-orcid":false,"given":"Pierre","family":"Vandenhove","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2022,1,17]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/8963\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/8963\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:19:45Z","timestamp":1687292385000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/7329"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,17]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(1:11)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"2001.03894v5","asserted-by":"subject"},{"id-type":"arxiv","id":"2001.03894v4","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2001.03894","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2001.03894","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2022,1,17]]},"article-number":"7329"}}