Concurrent Games with Arbitrarily Many Players - Archive ouverte HAL Access content directly
Conference Papers Year :

Concurrent Games with Arbitrarily Many Players



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.
Fichier principal
Vignette du fichier
Bertrand-mfcs20.pdf (447.16 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03095629 , version 1 (04-01-2021)


  • HAL Id : hal-03095629 , version 1


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⟩
35 View
50 Download


Gmail Facebook Twitter LinkedIn More