I am currently a F.R.S.-FNRS postdoctoral researcher. I am supervised by Thomas Brihaye in the Department of Mathematics of the University of Mons (UMONS).

From October 2021 to September 2022, I was a CNRS postdoctoral researcher at Irisa, Rennes (France), in the SUMO team. I worked with Nicolas Markey and Ocan Sankur on Timed Network Congestion Games.

During my PhD thesis (October 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).

Preprints

• Multi-Weighted Reachability Games: Thomas Brihaye and Aline Goeminne. to appear in RP'23. [Preprint on arXiv] [Abstract].

  We study two-player multi-weighted reachability games played on a finite directed graph, where an agent, called P1, has several quantitative reachability objectives that he wants to optimize against an antagonistic environment, called P2. In this setting, we ask what cost profiles P1 can ensure regardless of the opponent's behavior. Cost profiles are compared thanks to: (i) a lexicographic order that ensures the unicity of an upper value and (ii) a componentwise order for which we consider the Pareto frontier. We synthesize (i) lexico-optimal strategies and (ii) Pareto-optimal strategies. The strategies are obtained thanks to a fixpoint algorithm which also computes the upper value in polynomial time and the Pareto frontier in exponential time. Finally, the constrained existence problem is proved in P for the lexicographic order and PSPACE-complete for the componentwise order.

Conferences

• Non-Blind Strategies in Timed Network Congestion Games: Aline Goeminne, Nicolas Markey and Ocan Sankur, FORMATS'22. [Preprint on arXiv] [Abstract].

  Network congestion games are a convenient model for reasoning about routing problems in a network: agents have to move from a source to a target vertex while avoiding congestion, measured as a cost depending on the number of players using the same link. Network congestion games have been extensively studied over the last 40 years, while their extension with timing constraints were considered more recently. Most of the results on network congestion games consider blind strategies: they are static, and do not adapt to the strategies selected by the other players. We extend the recent results of [Bertrand et al., Dynamic network congestion games. FSTTCS'20] to timed network congestion games, in which the availability of the edges depend on (discrete) time. We prove that computing Nash equilibria satisfying some constraint on the total cost (and in particular, computing the best and worst Nash equilibria), and computing the social optimum, can be achieved in exponential space. The social optimum can be computed in polynomial space if all players have the same source and target.

• 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

• [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, Information and Computation, 2021, vol. 278, p. 104594.
• [Special issue] On Relevant Equilibria in Reachability Games: Thomas Brihaye, Véronique Bruyère, Aline Goeminne and Nathan Thomasset, Journal of Computer and System Sciences, 2021, vol. 119, p. 211-230.
• 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] 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, Logical Methods in Computer Science, 16, 4, 8:1-8:43 (2020).

• 2023: Highlights'23 (Kassel, Germany), Autobòz'23 (Kassel, Germany).
• 2022: LAMAS&SR'22 (Rennes, France), FORMATS'22 (Online), CONCUR'22 (Online).
• 2021: GT Verif 2021 (Online), FORMATS'21 (Online), CONCUR'21 (Online).
• 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) .

My talks (with slides).

Teaching

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.

Introductory research internship

• Gaëtan Staquet -- August 2018
  • Subject: "Algorithmes efficaces pour le calcul d'équilibres de Nash".
  • Other co-supervisors: Thomas Brihaye, Véronique Bruyère and Hadrien Mélot.
• Nicolas Lecomte -- August 2020
  • Subject: "Théorie des perspectives et théorie des jeux ".
  • Other co-supervisor: Thomas Brihaye

Master's thesis

• Louise Sadoine -- 2019-2020
  • Subject: " Les théories des perspectives appliquées aux jeux sous forme normale "
  • Other supervisor: Thomas Brihaye

You can contact me by:

• E-mail: aline.goeminne [at] umons.ac.be