Games Where You Can Play Optimally with Arena-Independent Finite Memory

Autor: Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, Pierre Vandenhove
Přispěvatelé: Laboratoire Méthodes Formelles (LMF), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Laboratoire d'Algorithmique Complexité et Logique (LACL), Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12), University of Mons [Belgium] (UMONS), Fonds National de la Recherche Scientifique [Bruxelles] (FNRS), Laboratoire Spécification et Vérification (LSV), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Institut de Mathématiques [Mons], Université de Mons (UMons), Fonds de la Recherche Scientifique [FNRS]
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Logical Methods in Computer Science
Logical Methods in Computer Science, 2022, Volume 18, Issue 1, ⟨10.46298/lmcs-18(1:11)2022⟩
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2022, Volume 18, Issue 1, ⟨10.46298/lmcs-18(1:11)2022⟩
31st International Conference on Concurrency Theory (CONCUR'20)
31st International Conference on Concurrency Theory (CONCUR'20), Sep 2020, Vienna, Austria. ⟨10.4230/LIPIcs.CONCUR.2020.18⟩
ISSN: 1860-5974
DOI: 10.46298/lmcs-18(1:11)2022
Popis: Updated title, full version of CONCUR 2020 conference paper; International audience; For decades, two-player (antagonistic) games on graphs have been a framework of choice for many important problems in theoretical computer science. A notorious one is controller synthesis, which can be rephrased through the game-theoretic metaphor as the quest for a winning strategy of the system in a game against its antagonistic environment. Depending on the specification, optimal strategies might be simple or quite complex, for example having to use (possibly infinite) memory. Hence, research strives to understand which settings allow for simple strategies. In 2005, Gimbert and Zielonka provided a complete characterization of preference relations (a formal framework to model specifications and game objectives) that admit memoryless optimal strategies for both players. In the last fifteen years however, practical applications have driven the community toward games with complex or multiple objectives, where memory -- finite or infinite -- is almost always required. Despite much effort, the exact frontiers of the class of preference relations that admit finite-memory optimal strategies still elude us. In this work, we establish a complete characterization of preference relations that admit optimal strategies using arena-independent finite memory, generalizing the work of Gimbert and Zielonka to the finite-memory case. We also prove an equivalent to their celebrated corollary of great practical interest: if both players have optimal (arena-independent-)finite-memory strategies in all one-player games, then it is also the case in all two-player games. Finally, we pinpoint the boundaries of our results with regard to the literature: our work completely covers the case of arena-independent memory (e.g., multiple parity objectives, lower- and upper-bounded energy objectives), and paves the way to the arena-dependent case (e.g., multiple lower-bounded energy objectives).
Databáze: OpenAIRE
Externí odkaz: