Positional Determinacy with Colored Vertices: a 1-to-2-Player Lift

Jul 16, 2026

Positional determinacy for vertex-colored parity games is studied through a 1-to-2-player lift for prefix-independent, color-based objectives over finite color sets. The work proves equivalence between positional determinacy of an objective W on all vertex-colored one-player games and on all vertex-colored two-player games. It further shows W matches a parity objective expressed by ordered pairs of colors, extending earlier edge-colored results. The equivalence relies essentially on finiteness of the color set and yields a bidirectional correspondence between edge- and vertex-colored games.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages20

Reading Time50 min

Introduction

Game setting and strategies

Colored objectives and traces

Parity objectives and prefix-independence

Positional determinacy and prior results

Illustrative example and arenas

arXiv :2607 .074 15v 1 [ cs .GT] 8 Jul 2026 Positional Determinacy with Colored Vertices: a 1-to-2-Player Lift Raphaël Berthon \# Ñ Université Paris-Saclay, CNRS, ENS Paris-Saclay, Laboratoire Méthodes Formelles, 91190, Gif-sur-Yvette, France Stéphane Le Roux \# Ñ Université Paris-Saclay, CNRS, ENS Paris-Saclay, Laboratoire Méthodes Formelles, 91190, Gif-sur-Yvette, France ~~ 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. 2012 ACM Subject Classification Theory of computation → Automata over infinite objects Keywords and phrases two-player games, one-player games, parity objectives Digital Object Identifier 10.4230/LIPIcs.CONCUR.2026.34 Funding Raphaël Berthon: [Funded by ANR-22-CE48-0012 (Bisous)] Stéphane Le Roux: [Funded by ANR-22-CE48-0012 (Bisous)] Acknowledgements Thanks to Bastien Laboureix for useful conversations. 1 Introduction Context: Game theory is applied to many fields such as economics, political science, evolutionary biology, and is used for model-checking processes in the industry [6] . While many game-theoretic models allow for multiple players and non-zero-sum payoffs, fundamental games in logic and computer science usually involve two players in a win-lose setting, where every play results in a win for exactly one player. In model checking, these win-lose games are typically turn-based and played on a finite or infinite labeled graph, called an arena. Starting from an initial vertex, the player owning the current vertex selects an outgoing edge to reach the next vertex. This continues indefinitely, producing an infinite path. A player’s strategy maps the history of visited vertices to her next move. Specifically, for every finite path ending at a vertex owned by that player, the strategy selects the edge to be followed. A pair of one strategy per player induces a unique infinite sequence of edges and vertices starting from the initial vertex, constituting the play. General strategies can be complex to implement: in a play of infinite duration, the number of distinct histories is infinite; therefore, implementing such a strategy generally requires a mechanism to store and process a history of unbounded length. Much work has thus focused © Raphaël Berthon and Stéphane Le Roux; licensed under Creative Commons License CC-BY 4.0 37th International Conference on Concurrency Theory (CONCUR 2026) . Editors: Ana Sokolova and Patrick Totzke; Article No. 34; pp. 34:1–34:20 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany 34:2 Positional Determinacy with Colored Vertices: a 1-to-2-Player Lift on strategies that require only finite memory, usually represented as a finite-state machine, or no memory at all. In the latter case, strategies map each position in the arena to a single outgoing edge, and are said to be positional (or memoryless) . The objective of the game is defined independently of the arena, as a set of infinite word

FAQs

What does the “1-to-2-Player lift” claim for vertex-colored games?

It shows that if a prefix-independent objective W is positionally determined for all vertex-colored one-player games, then it is also positionally determined for all vertex-colored two-player games, establishing an equivalence between the two settings.

How is the objective W related to parity objectives in the vertex-colored setting?

For any prefix-independent objective over a finite set of colors, the paper proves that positional determinacy on one-player and two-player vertex-colored games is equivalent to W being equivalent to a parity objective on ordered pairs of colors.

Why is finiteness of the color set required?

The paper demonstrates that finiteness is necessary for the equivalence to hold, indicating that the correspondence between vertex-colored and parity formulations can fail when the color set is infinite.

Jul 16, 2026

Upload by Seraphina