Thèse de Marc Heinrich


Sujet :
Problèmes de reconfiguration et jeux combinatoires

Résumé :

    Cette thèse explore des problématiques liées aux jeux. Nous nous intéressons en particulier aux jeux sans information cachée et sans aléa, à un ou deux joueurs.

    Les jeux à un joueur que nous considérons peuvent être décrit de la façon suivante : il y a un ensemble de configurations, qui représente tous les états possibles du jeu, et le joueur est autorisé à transformer une configuration en une autre via un certain nombre de règles. Le but est d'atteindre une configuration cible donnée à partir d'une configuration initiale. Les problèmes pouvant être définis avec ce formalisme sont appelés problèmes de reconfiguration, et incluent à la fois certains puzzles combinatoires tels que le Rubik's cube ou Rush-hour, mais également des transformations sur des problèmes de recherche pour lesquels l'ensemble des configurations est l'ensemble des solutions d'une instance d'un problème donné.

    Les jeux à deux joueurs qui nous intéressent sont appelés jeux combinatoires. Pour ces jeux là, nous considérons le cas où les joueurs jouent parfaitement, ce qui revient à tenter de caractériser lequel des joueurs possède une stratégie gagnante (qui lui assure la victoire quels que soient les coups de l'adversaire).

    Dans cette thèse, nous étudions ainsi des jeux à un et deux joueurs, et tout particulièrement la complexité de ceux-ci, c'est-à-dire évaluer à quel point il est difficile (d'un point de vue algorithmique) de calculer une stratégie gagnante. Plus précisément, nous étudions la reconfiguration de deux problèmes sur les graphes : les couplages parfaits et la coloration de graphes, pour lesquels nous donnons à la fois des preuves de difficulté à l'aide de réductions, et des algorithmes polynomiaux dans des sous-cas spécifiques. Nous nous intéressons aussi à deux problèmes en lien avec la reconfiguration : la génération aléatoire de coloration, via l'application de transformations aléatoires à une coloration donnée, et des algorithmes de coloration online. Enfin, la dernière partie de ces travaux porte sur les jeux combinatoires, pour lesquels nous nous concentrons plutôt sur des aspects structurels. Nous considérons tout d'abord les propriétés d'une famille de jeux particulière, les jeux de soustractions partisans, et étudions ensuite une construction générale pour combiner plusieurs règles de jeux, et en créer de nouvelles


Encadrant : Eric Duchene

Jury :
Celina De FigueiredoProfesseur(e)Université fénérale de Rio de JaneiroRapporteur(e)
Claire MathieuDirecteur(trice) de rechercheUniversité Paris 7Rapporteur(e)
Guerin-Lassous IsabelleProfesseur(e)Université Lyon 1Président(e)
Jan Van den HeuvelProfesseur(e)École d’économie et de science politique de LondresExaminateur​(trice)
Éric DuchêneMaître de conférenceUniversité Lyon 1Directeur(trice) de thèse
Sylvain GravierDirecteur(trice) de rechercheUniversité Grenoble AlpesCo-directeur (trice)
Nicolas BousquetChargé(e) de RechercheUniversité Grenoble AlpesCo-encadrant(e)