文章基本信息

标题：Synthesizing Safe Coalition Strategies
本地全文：下载
作者：Nathalie Bertrand ; Patricia Bouyer ; Anirban Majumdar 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：182
页码：1-17
DOI：10.4230/LIPIcs.FSTTCS.2020.39
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：concurrent games; parameterized verification; strategy synthesis