2026-07-25T14:45:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25084 2026-02-09T08:06:01Z ddc:004 open_access

Distributed Games with a Central Decision Maker Adsul, Bharat Jain, Nehul Mazurkiewicz traces models of concurrency distributed synthesis game-theoretic models asynchronous automata distributed decision-making We study distributed games played on non-deterministic asynchronous automata which feature a central decision maker process that participates in all key decision making tasks. In these partial-information games, processes use their causal past to respond to scheduling choices made by the scheduler and cooperatively strategize as a team to achieve the winning objective. We show that the problem of deciding the existence of a distributed winning strategy is efficiently solvable for global safety and local parity objectives. We provide algorithmic solutions that match their computational hardness. We formulate the notion of a finite-state distributed strategy which allows to quantify its distributed memory requirements. For the aforementioned objectives, we establish that finite-state distributed winning strategies always exist. In fact, we provide novel constructions of such winning strategies which are shown to have almost optimal amount of distributed memory. We also show that a natural extension of the model with two decision making processes is undecidable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bharat Adsul and Nehul Jain 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.5 urn:nbn:de:0030-drops-250843 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.5 eng https://creativecommons.org/licenses/by/4.0/legalcode