License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.1
URN: urn:nbn:de:0030-drops-126724
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12672/
Go to the corresponding LIPIcs Volume Portal

Bertrand, Nathalie

Concurrent Games with Arbitrarily Many Players (Invited Talk)

pdf-format:
LIPIcs-MFCS-2020-1.pdf (0.4 MB)

Abstract

Traditional concurrent games on graphs involve a fixed number of players, who take decisions simultaneously, determining the next state of the game. With Anirban Majumdar and Patricia Bouyer, we introduced a parameterized variant of concurrent games on graphs, where the parameter is precisely the number of players. Parameterized concurrent games are described by finite graphs, in which the transitions bear finite-word languages to describe the possible move combinations that lead from one vertex to another.
We report on results on two problems for such concurrent games with arbitrary many players. To start with, we studied the problem of determining whether the first player, say Eve, has a strategy to ensure a reachability objective against any strategy profile of her opponents as a coalition. In particular Eve’s strategy should be independent of the number of opponents she actually has. We establish the precise complexities of the problem for reachability objectives. Second, we considered a synthesis problem, where one aims at designing a strategy for each of the (arbitrarily many) players so as to achieve a common objective. For safety objectives, we show that this kind of distributed synthesis problem is decidable.

BibTeX - Entry

@InProceedings{bertrand:LIPIcs:2020:12672,
  author =	{Nathalie Bertrand},
  title =	{{Concurrent Games with Arbitrarily Many Players (Invited Talk)}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{1:1--1:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12672},
  URN =		{urn:nbn:de:0030-drops-126724},
  doi =		{10.4230/LIPIcs.MFCS.2020.1},
  annote =	{Keywords: concurrent games, parameterized verification}
}

Keywords: concurrent games, parameterized verification
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI