{"ID":6138267,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T13:31:09.21043372Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07415","arxiv_id":"2607.07415","title":"Positional Determinacy with Colored Vertices: a 1-to-2-Player Lift","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2607.07415","url_pdf":"https://arxiv.org/pdf/2607.07415v1","authors":"[\"Raphaël Berthon\",\"Stéphane Le Roux\"]","published":"2026-07-08T13:46:35Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}