Positionality in Σ_0^2 and a completeness result
This work addresses foundational questions in game theory and automata theory, providing criteria for positional strategies in infinite games, which is incremental but builds on prior results.
The paper tackles the problem of identifying which infinite-duration game objectives guarantee positional strategies for the protagonist over arbitrary game graphs, proving that such objectives are exactly those recognized by history-deterministic monotone co-Büchi automata over countable ordinals. It applies this result to show that the mean-payoff objective is positional over arbitrary graphs and establishes a completeness result for extending positional strategies from finite to arbitrary graphs.
We study the existence of positional strategies for the protagonist in infinite duration games over arbitrary game graphs. We prove that prefix-independent objectives in Σ_0^2 which are positional and admit a (strongly) neutral letter are exactly those that are recognised by history-deterministic monotone co-Büchi automata over countable ordinals. This generalises a criterion proposed by [KopczyÅski, ICALP 2006] and gives an alternative proof of closure under union for these objectives, which was known from [Ohlmann, TheoretiCS 2023]. We then give two applications of our result. First, we prove that the mean-payoff objective is positional over arbitrary game graphs. Second, we establish the following completeness result: for any objective W which is prefix-independent, admits a (weakly) neutral letter, and is positional over finite game graphs, there is an objective W' which is equivalent to W over finite game graphs and positional over arbitrary game graphs.