2026-07-22T07:15:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13280 2024-03-06T10:52:01Z ddc:004 open_access

Synthesizing Safe Coalition Strategies Bertrand, Nathalie Bouyer, Patricia Majumdar, Anirban concurrent games parameterized verification strategy synthesis Concurrent games with a fixed number of agents have been thoroughly studied, with various solution concepts and objectives for the agents. In this paper, we consider concurrent games with an arbitrary number of agents, and study the problem of synthesizing a coalition strategy to achieve a global safety objective. The problem is non-trivial since the agents do not know a priori how many they are when they start the game. We prove that the existence of a safe arbitrary-large coalition strategy for safety objectives is a PSPACE-hard problem that can be decided in exponential space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathalie Bertrand and Patricia Bouyer and Anirban Majumdar 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.39 urn:nbn:de:0030-drops-132807 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.39 eng https://creativecommons.org/licenses/by/3.0/legalcode