2026-08-25T22:09:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27348 2026-08-24T14:08:30Z ddc:004 open_access

Positional Determinacy with Colored Vertices: A 1-To-2-Player Lift Berthon, Raphaël Le Roux, Stéphane two-player games one-player games parity objectives 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Raphaël Berthon and Stéphane Le Roux 2026 Is Part Of LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2026.17 urn:nbn:de:0030-drops-273480 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.17 eng https://creativecommons.org/licenses/by/4.0/legalcode