During my PhD thesis (Octobre 2017 to April 2021), I was co-supervised by Thomas Brihaye in the Department of Mathematics of the University of Mons (UMONS) and Jean-François Raskin in the Computer Science Department of the Université libre de Bruxelles (ULB).
My research interests lie in the fields of Game Theory and Formal Verification. In particular, I am interested in the synthesis of equilibria in multi-player non-zero sum games (e.g., Nash Equilibria, Subgame Perfect Equilibria and weak Subgame Perfect Equilibria).
We study multiplayer turn-based timed games with reachability objectives. In particular, we are interested in the notion of subgame perfect equilibrium (SPE). We prove that deciding the constrained existence of an SPE in this setting is EXPTIME-complete.
We study multiplayer reachability games played on a finite directed graph equipped with target sets, one for each player. In those reachability games, it is known that there always exists a Nash equilibrium (NE) and a subgame perfect equilibrium (SPE). But sometimes several equilibria may coexist such that in one equilibrium no player reaches his target set whereas in another one several players reach it. It is thus very natural to identify ``relevant'' equilibria. In this paper, we consider different notions of relevant equilibria including Pareto optimal equilibria and equilibria with high social welfare. We provide complexity results for various related decision problems.
We study multiplayer quantitative reachability games played on a finite directed graph, where the objective of each player is to reach his target set of vertices as quickly as possible. Instead of the well-known notion of Nash equilibrium (NE), we focus on the notion of subgame perfect equilibrium (SPE), a refinement of NE well-suited in the framework of games played on graphs. It is known that there always exists an SPE in quantitative reachability games and that the constrained existence problem is decidable. We here prove that this problem is PSPACE-complete. To obtain this result, we propose a new algorithm that iteratively builds a set of constraints characterizing the set of SPE outcomes in quantitative reachability games. This set of constraints is obtained by iterating an operator that reinforces the constraints up to obtaining a fixpoint. With this fixpoint, the set of SPE outcomes can be represented by a finite graph of size at most exponential. A careful inspection of the computation allows us to establish PSPACE membership.
We study multiplayer turn-based games played on a finite directed graph such that each player aims at satisfying an omega-regular Boolean objective. Instead of the well-known notions of Nash equilibrium (NE) and subgame perfect equilibrium (SPE), we focus on the recent notion of weak subgame perfect equilibrium (weak SPE), a refinement of SPE. In this setting, players who deviate can only use the subclass of strategies that differ from the original one on a finite number of histories. We are interested in the constrained existence problem for weak SPEs. We provide a complete characterization of the computational complexity of this problem: it is P-complete for Explicit Muller objectives, NP-complete for Co-Büchi, Parity, Muller, Rabin, and Streett objectives, and PSPACE-complete for Reachability and Safety objectives (we only prove NP-membership for Büchi objectives). We also show that the constrained existence problem is fixed parameter tractable and is polynomial when the number of players is fixed. All these results are based on a fine analysis of a fixpoint algorithm that computes the set of possible payoff profiles underlying weak SPEs.
We study multiplayer turn-based games played on a finite directed graph and such that each player has a Büchi objective, i.e., each player is equipped with a subset of vertices of the graph that he wants to reach infinitely often. Instead of studying the well known notions of Nash equilibrium (NE) and subgame perfect equilibrium (SPE), we focus on the notion of weak subgame equilibrium (weak SPE). In this setting, players who deviate can only use the subclass of strategies that differ from the original one on a finite number of histories. We are interesting in a decision problem called the constrained existence problem that we prove to be P-complete for multiplayer games with Büchi objectives.
|Calculability and complexity||Teaching Assistant||4th year||September 2019 - December 2021||
I give exercise sessions of the "Calculability and complexity" course (ULB) given by Jean-François Raskin.
|Mathématiques effectives||Teaching Assistant||Maths: 4th year||September 2018 - June 2021||
I give exercise sessions of the "Mathématiques effectives" course - a course about Game Theory given by Thomas Brihaye.