Au vu des mesures de confinement actuelles, la défense aura lieu par vidéo-conférence via le lien suivant :

https://youtu.be/BjmRlPOq-Gw

Promoteur de la thèse: Monsieur Thomas BRIHAYE

Résumé de la dissertation: Since the seminal works of Morgenstern and von Neuman in the forties, game theory has emerged as a prominent paradigm to model the behaviour of rational and selfish agents acting in a competitive setting. In particular, it has been applied to computer sciences. In this context, several agents (called players) usually model different components of a computer system (and of its environment). They are assumed to be rational, and interact in order to reach a fixed objective.
In this thesis, we are concerned with multi-player games played on graphs. They are games in which n ≥ 2 players interact trying to fulfill their own objective (which are not necessarily antagonistic to the others); and where the arena (defining the possible actions of the players) is given as a finite graph. Every node of the graph is owned by a player. The game is played by
letting players move a token along the edges of the arena.
The point of this thesis is to study the notion of dynamics in games which models the
behaviour of the players when they repeatedly update their strategy (i.e. their choices of actions) in order to achieve a better outcome. The idea behind the notion of dynamics is the following : the game is played once with a strategy profile for the players. One (or several) player is not satisfied with his strategy (because he could have chose a better strategy, due to the choice of the other players). Then the game is played a second time, with the new strategy profile. Maybe another player will be unsatisfied with his strategy and the game will be played once again. We say that a dynamics terminates when these updates converge to an equilibrium, i.e. a state in which the players have no incentive to further update their respective strategies.
We define several properties that a dynamics has to satisfy or not. For example, we can
require that a dynamics satisfy the one player property, which means that each update has to be performed by a unique player at a time. Another possible requirement the lazy property, which means that the players updating their strategy perform it with the minimal number of changes.
There are two kinds of contributions in the thesis. The first one is to draw a general frame-
work to reason about the termination of dynamics in order to show its applicability to particular problems. It relies on notions of preorders, in particular the simulation preorder. Simulations are usually defined on transition systems: intuitively, a system A simulates a system B if each step of B can be mimicked in A. We consider two kinds of preorders: preorders defined on game graphs, i.e. on the structure of the games; and simulations defined on the dynamics, which are useful to reason about termination (indeed, if a dynamics D1 simulates a dynamics D2 , and if D1 terminates, then D2 terminates as well). We show how the existence of a relation between game graphs implies the existence of a simulation between the induced dynamics of those games.
This technique allows us to check the termination of the dynamics using structural criteria about the game graph.
The second kind of contribution is the application to a particular context, characterised by
three parameters : the arena of the game, the conditions over the dynamics, and the payo_
functions of the players.
The first arena we deal with are sequential games (or games played on tree). Among other
results, we prove that the acyclicity of the preferences is a necessary and sufficient condition to ensure the termination of dynamics that respect the Subgame Improvement Property (i.e. every update has to improve the payoff in the subgame of the change). We also consider the so called Coalitional Dynamics (in which several players can make coalitions in order to update their strategies) and discover a pattern over the preferences of the players that has to be avoided.
The second arena is the so called One-player Games. We model BGP (Border Gateway
Protocol, which is standard interdomain routing protocol) into dynamics on graphs. We firstly
revisit some classical results of network theory in our context, then we identify a theoretical, relevant framework regarding to the termination of the dynamics.
We also make the first step in a broader context, considering some games played on graph,
such as reachability games and mean-payoff games. We only obtained some results of termination.