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

Raphaël Berthon, Stéphane Le Roux

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 strengthen this result by restricting the requirement to one-player games. Similarly, for vertex-colored games, we prove 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 pairs of colors. We prove that finiteness is required for our second equivalence to hold. Beyond these two 1-to-2-player lifts, the technique that we develop to handle the pairs of colors establishes a (potentially strong) 2-way correspondence between edge-colored games and vertex-colored games.

Other talks in CONCUR Session 1 - Stochastic Games & MDPs I:

• Asymmetrically-Discounted Stochastic Games
• Probabilistic Model Checking via Families of Deterministic and Unambiguous Finite Automata
• Mean-Payoff-Parity and Lifting Strategies from MDPs to 2-Player Stochastic Games

 Program   CONCUR Program