Léonard BRICE - Faculté des Sciences

Titre de la thèse: "Equilibria in Multiplayer Graph Games. An Algorithmic Study"
Résumé: 
Pour vérifier la robustesse d’un programme ou d’un protocole, il est courant dans la communauté
informatique de s’appuyer sur le cadre théorique de la théorie des jeux. En particulier, lorsqu’on cherche à
programmer un système de sorte à garantir une certaine propriété, ou spécification, malgré un environnement
imprévisible, une abstraction utile consiste à modéliser la situation comme un jeu à somme nulle
à deux joueurs. L’objectif est alors de trouver une stratégie pour le système qui assure la spécification
contre toute stratégie de l’environnement. Cependant, pour modéliser des situations plus complexes, par
exemple plusieurs systèmes poursuivant des objectifs distincts ou un environnement composé de divers
agents, il est nécessaire de considérer le cadre plus riche des jeux multijoueurs. Dans ce contexte, une
question naturelle est d’identifier des équilibres, c’est-à-dire des profils de stratégies robustes, en ce sens
qu’aucun joueur n’a intérêt à en dévier. Le concept d’équilibre le plus connu est l’équilibre de Nash, mais
plusieurs alternatives existent. Nous étudions cinq de ces notions et, pour chacune d’elles, nous établissons
des résultats de complexité pour le problème d’existence contrainte, qui consiste à décider si un jeu donné
contient un équilibre garantissant à chaque joueur un gain situé dans un intervalle spécifié.
Nous montrons ainsi quelques résultats pour ce problème concernant les équilibres de Nash, bien que
ceux-ci aient déjà largement été étudiés.
La partie principale de notre contribution porte sur les équilibres parfaits en sous-jeu (ou subgameperfect
equilibria, SPEs), un raffinement des équilibres de Nash dans les jeux séquentiels qui élimine les
menaces non crédibles en exigeant que les stratégies prévues par tous les joueurs forment toujours un
équilibre de Nash après toute suite d’actions possible. Nous donnons des bornes de complexité précises
pour le problème d’existence contrainte des SPEs dans quatre classes de jeux classiques de la théorie des
jeux. Nous explorons ensuite la relation entre le problème d’existence contrainte et une question connexe,
la vérification rationnelle, qui consiste à vérifier si une stratégie donnée garantit une propriété spécifiée
contre toutes les réponses rationnelles, définies en termes d’équilibres de Nash ou de SPEs. Dans les cas
où il n’est pas garanti que des réponses rationnelles existent, comme c’est le cas des SPEs dans les jeux
mean-payoff, nous proposons une définition alternative de la vérification rationnelle, selon laquelle la
spécification doit être satisfaite contre toute réponse aussi rationnelle que possible, en utilisant la notion
d’��-SPE—et nous donnons, là encore, des resultats de complexité pour ce problème.
Une troisième notion que nous étudions est celle d’équilibre sécurisé fort (ou strong secure equilibrium,
SSE), où aucune coalition de joueurs ne peut nuire à un autre joueur sans nuire également à au moins
un de ses propres membres. En plus de plusieurs résultats de complexité, nous montrons que les SSEs
permettent de modéliser une notion pertinente et flexible de protocoles sécurisés impliquant des agents
non fiables.