2026-07-22T17:01:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19661 2024-03-06T11:04:35Z ddc:004 open_access

From Local to Global Optimality in Concurrent Parity Games Bordais, Benjamin Bouyer, Patricia Le Roux, Stéphane Game forms stochastic games parity games Blackwell/Martin values 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Bordais and Patricia Bouyer and Stéphane Le Roux 2024 Is Part Of LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2024.18 urn:nbn:de:0030-drops-196612 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.18 eng https://creativecommons.org/licenses/by/4.0/legalcode