Aline Goeminne

Publications

Preprints

Conferences

• On Subgame Perfect Equilibria in Turn-Based Reachability Timed Games:Thomas Brihaye and Aline Goeminne, FORMATS'20. [Preprint on arXiv] [Abstract].

  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.

• On Relevant Equilibria in Reachability Games: Thomas Brihaye, Véronique Bruyère, Aline Goeminne and Nathan Thomasset, RP'19. [Extended version on arXiv] [Abstract].

  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.

• The Complexity of Subgame Perfect Equilibria in Quantitative Reachability Games: Thomas Brihaye, Véronique Bruyère, Aline Goeminne, Jean-François Raskin and Marie van den Bogaard, CONCUR'19, [Extended version on arXiv] [Abstract].

  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.

• Constrained Existence Problem for Weak Subgame Perfect Equilibria with ω-regular Boolean Objectives: Thomas Brihaye, Véronique Bruyère, Aline Goeminne and Jean-François Raskin, GandALF'18 [Extended version on arXiv] [Abstract].

  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.

Journals

• Constrained Existence of weak Subgame Perfect Equilibria in Multiplayer Büchi games: Aline Goeminne, Information Processing Letters Volume 163, November 2020. [Abstract].

  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.

• [Special issue] Constrained Existence Problem for Weak Subgame Perfect Equilibria with ω-regular Boolean Objectives: Thomas Brihaye, Véronique Bruyère, Aline Goeminne and Jean-François Raskin, to appear in Information and Computation.
• [Special issue] The Complexity of Subgame Perfect Equilibria in Quantitative Reachability Games: Thomas Brihaye, Véronique Bruyère, Aline Goeminne, Jean-François Raskin and Marie van den Bogaard, to appear in Logical Methods in Computer Science

Attended events

• 2020: HIGHLIGHTS'20 (Online), FORMATS'20 (Online), MOVEP (Online).
• 2019: Grascomp Doctoral Day (GDD’19) (Namur, Belgium), HIGHLIGHTS'19 (Warsaw, Poland), RP'19 (Bruxelles, Belgium), CONCUR'19 (Amsterdam, Netherlands), Theory and Algorithms in Graph and Stochastic Games (Mons, Belgium), Mardi des Chercheurs 2019 (Mons, Belgium).
• 2018: GandALF 2018 (Saarbrücken, Germany), HIGHLIGHTS 2018 (Berlin, Germany), MOVEP (ENS Cachan, France), MoRe at FLoC 2018 (University of Oxford, UK), Logic and learning at FoPPS 2018 (University of Oxford, UK), GT Verif 2018 (VERIMAG, Grenoble, France) .
• 2017: HIGHLIGHTS 2017 (London, UK) .

Teaching

Miscellaneous