Publications

Preprints

• Permissive Equilibria in Multiplayer Reachability Games: Aline Goeminne and Benjamin Monmege, to appear in CSL'25.
• Multi-Weighted Reachability Games and Their Application to Permissiveness: Thomas Brihaye and Aline Goeminne. [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. The constrained existence problem is proved in P for the lexicographic order and PSPACE-complete for the componentwise order. Finally, we show how complexity results about permissiveness of multi-strategies in two-player quantitative reachability games can be derived from the results we obtained in the two-player multi-weighted reachability games setting.

Invited papers in international conferences

• Reachability Games and Friends : A Journey through the Lens of Memory and Complexity, Thomas Brihaye, Aline Goeminne, James C.A. Main and Mickael Randour, Keynote lecture given by Thomas Brihaye at FSTTCS'23, LIPIcs 284, Schloss Dagstuhl 2023. [DOI] [Abstract].

  Reachability objectives are arguably the most basic ones in the theory of games on graphs (and beyond). But far from being bland, they constitute the cornerstone of this field. Reachability is everywhere, as are the tools we use to reason about it. In this invited contribution, we take the reader on a journey through a zoo of models that have reachability objectives at their core. Our goal is to illustrate how model complexity impacts the complexity of strategies needed to play optimally in the corresponding games and computational complexity.

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. [DOI]
• [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. [DOI]
• Constrained Existence of weak Subgame Perfect Equilibria in Multiplayer Büchi games: Aline Goeminne, Information Processing Letters Volume 163, November 2020. [DOI] [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). [DOI]

Conferences

• Multi-Weighted Reachability Games: Thomas Brihaye and Aline Goeminne. RP'23, LNCS 14235, pages 85-97, Springer, 2023. [DOI][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.

• Non-Blind Strategies in Timed Network Congestion Games: Aline Goeminne, Nicolas Markey and Ocan Sankur, FORMATS'22, LNCS 13465, pages 183-199, Springer, 2022. [DOI][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, LNCS 12288, pages 94-110, Springer 2020. [DOI][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, LNCS 11674, pages 48-62, Springer, 2019. [DOI][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, LIPIcs 140, pages 13:1-13-16, Schloss Dagstuhl, 2019. [DOI][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 , EPTCS 277, pages 16-29, 2018. [DOI][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.

PhD Thesis

Title Equilibria in Multiplayer Games Played on Graphs
Université de Mons (UMONS) et Université de Bruxelles (ULB), 346 pages, 2021.
Supervisors Thomas Brihaye (UMONS) and Jean-François Raskin (ULB)
Jury Thomas Brihaye (UMONS), Véronique Bruyère (UMONS), János Flesch (Maastricht University, the Netherlands), Gilles Geeraerts (ULB), Jean-François Raskin (ULB) and Ocan Sankur (Université de Rennes, CNRS, France).
Started on October 1, 2017
Graduation April 27, 2021
Manuscript available [here]