2026-07-21T20:32:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15552 2024-03-06T10:55:34Z ddc:004 open_access

From Local to Global Determinacy in Concurrent Graph Games Bordais, Benjamin Bouyer, Patricia Le Roux, Stéphane Concurrent games Game forms Local interaction In general, finite concurrent two-player reachability games are only determined in a weak sense: the supremum probability to win can be approached via stochastic strategies, but cannot be realized. We introduce a class of concurrent games that are determined in a much stronger sense, and in a way, it is the largest class with this property. To this end, we introduce the notion of local interaction at a state of a graph game: it is a game form whose outcomes (i.e. a table whose entries) are the next states, which depend on the concurrent actions of the players. By definition, a game form is determined iff it always yields games that are determined via deterministic strategies when used as a local interaction in a Nature-free, one-shot reachability game. We show that if all the local interactions of a graph game with Borel objective are determined game forms, the game itself is determined: if Nature does not play, one player has a winning strategy; if Nature plays, both players have deterministic strategies that maximize the probability to win. This constitutes a clear-cut separation: either a game form behaves poorly already when used alone with basic objectives, or it behaves well even when used together with other well-behaved game forms and complex objectives. Existing results for positional and finite-memory determinacy in turn-based games are extended this way to concurrent games with determined local interactions (CG-DLI). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Bordais and Patricia Bouyer and Stéphane Le Roux 2021 Is Part Of LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2021.41 urn:nbn:de:0030-drops-155522 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.41 eng https://creativecommons.org/licenses/by/4.0/legalcode