New Math Breakthrough Could Make Computers Better at Strategy

This paper studies positional determinacy of infinite-duration games played on potentially infinite graphs with neutral transitions. It proposes two notions of infinite lexicographic products indexed by arbitrary ordinals and extends Ohlmann’s 2023 result by proving that these products also preserve positionality.

In the one-player positionality context, this extends Grädel and Walukiewicz’s 2006 positional determinacy results to edge-labelled games and arbitrarily many priorities for both Max-Parity and Min-Parity. The authors also show that Max-Parity objectives over countable ordinals are complete for the infinite levels of the difference hierarchy over Σ^0_2, and that Min-Parity is complete for Σ^0_3. They therefore obtain positional languages that are complete for all those levels, as well as new insights about closure under unions and neutral letters.