Positional Determinacy with Colored Vertices: a 1-to-2-Player Lift
This resolves a theoretical question about the relationship between one-player and two-player determinacy in vertex-colored games, providing a complete characterization for finite color sets.
The authors prove that for prefix-independent objectives over finite color sets, positional determinacy in vertex-colored one-player games is equivalent to positional determinacy in vertex-colored two-player games, and both are equivalent to a parity objective on ordered pairs of colors. They also show finiteness of the color set is necessary for this equivalence.
Positional determinacy of vertex-colored parity games was proved in the 1990s, which directly implies positional determinacy of edge-colored parity games. In 2006, it was shown that if a prefix-independent color-based objective ensures that every edge-colored two-player turn-based game is positionally determined, this objective is equivalent to a parity objective. We prove a similar result for vertex-colored games, namely that the following are equivalent for any prefix-independent objective $W$ over a finite set of colors: - $W$ is positionally determined on all vertex-colored one-player games. - $W$ is positionally determined on all vertex-colored two-player games. - $W$ is equivalent to a parity objective on ordrerd pairs of colors. We prove that finiteness of the color set is required for our equivalence to hold. Beyond this $1$-to-$2$-player lift, the technique that we develop to handle the pairs of colors establishes a promising 2-way correspondence between edge-colored games and vertex-colored games.