From Local to Global Optimality in Concurrent Parity Games

We study two-player games on finite graphs. Turn-based games have many nice properties, but concurrent games are harder to tame: e. g. turn-based stochastic parity games have positional optimal strategies, whereas even basic concurrent reachability games may fail to have optimal strategies. We study concurrent stochastic parity games, and identify a local structural condition that, when satisfied at each state, guarantees existence of positional optimal strategies for both players.

Authors

• Benjamin Bordais
• Patricia Bouyer
• Stéphane Le Roux 0001

Keywords

• Game forms
• stochastic games
• parity games
• Blackwell/Martin values