Concurrent two-player antagonistic games on graphs
by Benjamin Bordais
Thursday 12 October 2023 at 2PM
ENS Paris-Saclay, room 1Z56
Abstract. We study two-player antagonistic games on graphs. In such a setting, two players, Player A and Player B, start at a given state of a graph and then concurrently interact to choose a probability distribution over successor states. This process is then repeated indefinitely, thus creating an infinite sequence of states: the outcome of game. That outcome is mapped by a payoff function to a value between 0 and 1 that Player A wants to maximize, while Player B wants to minimize it.
Turn-based games are a special kind of concurrent games: at each state, only one player chooses the probability distribution over successor states. For many desirable properties, such as the existence of winning strategies in deterministic games, even very simple concurrent games behave much more poorly than arbitrary turn-based games.
The goal of this PhD was to define a restriction of the kind of interactions appearing at each state of concurrent games to obtain a proper superclass of turn-based games that still behaves like turn-based games. To achieve this goal, we have developed several useful tools on concurrent games. In particular, we have adapted and slightly extended the famous theorem by Martin on the determinacy of Blackwell games, of which I will discuss. I will then present some of the restrictions on the local interactions that I described in my PhD thesis.
Supervisors:
- Patricia Bouyer-Decitre, CNRS, LMF, France
- Stéphane Le Roux, ENS Paris-Saclay, LMF, France
Jury:
- Richard Mayr , University of Edinburgh, UK -- Rapporteur
- Benjamin Monmege, Aix-Marseille Université, LIS, France -- Rapporteur
- Krishnendu Chatterjee, IST Austria
- Serge Haddad, ENS Paris-Saclay, LMF, France
- Marta Kwiatkowska, University of Oxford, UK
- Sophie Pinchinat, Université de Rennes 1, IRISA, France
- Bruno Ziliotto, CNRS, CEREMADE, France