Skip to Main content Skip to Navigation
Conference papers

Concurrent Games with Arbitrarily Many Players

Nathalie Bertrand 1
1 SUMO - SUpervision of large MOdular and distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03095629
Contributor : Nathalie Bertrand Connect in order to contact the contributor
Submitted on : Monday, January 4, 2021 - 4:50:41 PM
Last modification on : Thursday, January 20, 2022 - 4:16:17 PM
Long-term archiving on: : Monday, April 5, 2021 - 9:14:32 PM

File

Bertrand-mfcs20.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03095629, version 1

Citation

Nathalie Bertrand. Concurrent Games with Arbitrarily Many Players. MFCS 2020 - 45th International Symposium on Mathematical Foundations of Computer Science, Aug 2020, Prague, Czech Republic. pp.1-8. ⟨hal-03095629⟩

Share

Metrics

Les métriques sont temporairement indisponibles