Games with a parameterized number of players

Nathalie Bertrand
INRIA Rennes
Friday, 5 June, 2020 - 14:00
BigBlueButton (Online)

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 introduce 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 so-called parameterized concurrent games. To start with, we tackled 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 parameterized reachability game problem. Second, we consider a synthesis problem, where one aims at designing a strategy for each of the players so as to achieve a common objective. For safety objectives, we show that this kind of distributed synthesis problem is decidable.

The meeting will be held online on BigBlueButton. To join use the following link in Chrome or Firefox: https://wc1.math.uca.fr/b/nat-6qe-4gg

The meeting password is 788304