Date: Tuesday, March 18, 2025 – 13h00
Place: B013 (Bob)
Title: On reachability games played on graphs
Nowadays computer systems are more and more involved in our everyday life. These systems become increasingly complex and interact either together or with humans. Moreover, in some situations bugs may have dramatic consequences. Thus, given a system, one wants to ensure that this system satisfies some specifications.
Two-player zero-sum games played on graphs are commonly used to model reactive systems where a system interacts with its environment. In such a setting, a player represents the system and wants to achieve an objective, i.e., to satisfy a specification, and another player represents the environment and acts in an antagonistic way. With this point of view, one wants to synthesize a strategy of the system player such that if he complies with this strategy, he can ensure to achieve his objective whatever the behavior of the environment player. However this model may be too restrictive as it does not allow to model situations involving more than two agents. Thus, the model evolves from two-player zero-sum games to multiplayer games where all players have their own objectives not necessarily antagonistic. The most famous solution concepts studied in multiplayer games are those of equilibria, e.g., Nash equilibria (NEs).
In this talk, I will provide an overview of the kinds of problems I have studied so far and I will explain how they can be solved. In particular, I will focus on multiplayer games played on graphs such that each player has a reachability objective. A player with a qualitative objective aims at reaching a given subset of vertices, called his target set. When weights are assigned to the edges of the game graph, the particular case of quantitative reachability objective may be studied. Roughly speaking, a player equipped with such an objective wants to minimize the cumulative weights until a vertex of his target set is reached. In the multiplayer setting, we are interested in deciding the existence of an equilibrium such that: (in the qualitative setting) a given subset of players have to reach their target set; or (in the quantitative setting) players have to reach their target set within a given number of steps. For NEs, these problems have been proven to be NP-complete.
Joint with the Veridis seminar.
