2023/11/24 by Bordais, Benjamin, Bouyer, Patricia, Roux, Stéphane Le
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2311.14373
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.