一句话：完整刻画了允许双方用与竞技场无关的有限内存取得最优策略的偏好关系。
图上的双人对抗博弈是控制器综合等问题的重要框架，但最优策略需要多少内存长期缺乏完整判据。Gimbert 与 Zielonka 在 2005 年刻划了允许无内存最优策略的偏好关系；近十五年应用推动多目标博弈，有限内存几乎总是必需，但其精确边界未知。本文完整刻划了允许使用与竞技场无关的有限内存取得最优策略的偏好关系，将 Gimbert–Zielonka 的结果推广到有限内存情形。作者还证明对应推论：若双方在所有单玩家博弈中都有此类最优策略，则所有双玩家博弈中也如此。结果覆盖多奇偶目标、有上下界能量目标等，并为依赖竞技场内存的情形铺路。
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).
@article{paperbot1744,
title = {Games Where You Can Play Optimally with Arena-Independent Finite Memory},
author = {Patricia Bouyer and Stéphane Le Roux and Youssouf Oualhadj and Mickael Randour and Pierre Vandenhove},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 1},
year = {2022},
doi = {10.46298/lmcs-18(1:11)2022}
}