We consider zero-sum games on infinite graphs, with objectives specified as sets of infinite words over some alphabet of colors. A well-studied class of objectives is the one of $\omega$-regular objectives, due to its relation to many natural problems in theoretical computer science. We focus on the strategy complexity question: given an objective, how much memory does each player require to play as well as possible? A classical result is that finite-memory strategies suffice for both players when the objective is $\omega$-regular. We show a reciprocal of that statement: when both players can play optimally with a chromatic finite-memory structure (i.e., whose updates can only observe colors) in all infinite game graphs, then the objective must be $\omega$-regular. This provides a game-theoretic characterization of $\omega$-regular objectives, and this characterization can help in obtaining memory bounds. Moreover, a by-product of our characterization is a new one-to-two-player lift: to show that chromatic finite-memory structures suffice to play optimally in two-player games on infinite graphs, it suffices to show it in the simpler case of one-player games on infinite graphs. We illustrate our results with the family of discounted-sum objectives, for which $\omega$-regularity depends on the value of some parameters.
翻译:我们考虑的是无限图形上的零和游戏, 其目标由一些颜色字母的无限字数来指定。 一个经过很好研究的目标类别是一个固定目标, 因为它与理论计算机科学中许多自然问题的关系。 我们关注的是战略的复杂性问题: 给一个目标, 每个玩家需要多少记忆来尽可能玩游戏? 一个典型的结果是, 当目标为$\ omega$- 常规时, 两个玩家的有限和游戏策略就足够了。 我们的描述的副产品是一个新的一对二的参数提升: 当两个玩家都可以在所有无限游戏图中以色化的限定和模数结构( 即, 其更新只能观察颜色) 来最佳地玩一个固定目标, 然后目标必须是 $\ omega$- 常规目标的游戏的理论性描述, 并且这种描述可以帮助获得记忆的界限。 此外, 我们的描述的副产品是一个新的一对二玩家的参数提升: 在游戏的游戏中, 显示一个游戏的极值- 游戏的极值结构结构结构, 足以以最优的方式在游戏中显示一个游戏的模型中, 。