Stratégies à mémoire finie dans les jeux concurrents à deux joueurs.
Jeudi 21 décembre 2023 à 14h00
ENS Paris-Saclay, Salle 1Z71, zoom
Résumé. On étudie des jeux concurrents à deux joueurs de durée infinie qui se jouent de la façon suivante : chaque tour, les deux joueurs choisissent chacun une action sans connaître le choix actuel de l'adversaire. Sur un nombre de tours infini, cette procédure génère une suite infinie de paires d'actions. Cette suite est alors gagnante pour le Joueur 1 si elle appartient à l'ensemble gagnant du jeu.
Dans ce type de jeux, il existe différent types de stratégies souhaitables selon les garanties qu'elles offrent au Joueur 1 sur la probabilité de gagner : les stratégies gagnantes, gagnantes presque sûrement, optimales, et quasi-optimales. Seules les stratégies quasi-optimales existent dans tous les jeux. Toutefois, ces stratégies souhaitables peuvent être très complexes et ne peuvent pas toujours être représentées par un objet fini. L'existence de stratégies qui sont à la fois souhaitables et simples est une question récurrente de la théorie des jeux pour l'informatique. Une interprétation standard de stratégies simples est celle des stratégies à mémoire finie, qui peuvent être représentées comme des machines à états finis.
On cherche à montrer des résultats de transfert de la forme suivante : étant données certaines hypothèses sur l'ensemble gagnant, si le Joueur 1 a une stratégie souhaitable d'un type donné (gagnante, presque sûrement gagnante, optimale ou quasi-optimale), alors il en a une à mémoire finie. On s'intéresse à deux classes d'hypothèses importantes sur les ensembles gagnants. D'une part, l'hypothèse de bel ordre, qui se rapporte aux ensembles gagnants résiduels et qui est satisfaite par des objectifs classiques de la littérature sur les jeux sur des graphes finis. D'autre part, on contraint la "forme" de l'ensemble gagnant en utilisant à la fois des éléments de la théorie descriptive des ensembles et des éléments de la théorie des jeux pour l'informatique. En particulier, on introduit une nouvelle opération sur les ensembles, l'interfoliage, inspirée de la hiérarchie des différences des ouverts de Hausdorff. Enfin, on étudie également les relations entre notre modèle de jeux et celui des jeux sur graphes, plus populaire dans la littérature sur la théorie des jeux pour l'informatique.
Composition du Jury :
- Jacques Duparc, École Polytechnique Fédérale de Lausanne - rapporteur
- Nathanaël Fijalkow, CNRS - rapporteur
- Nathalie Bertrand, Inria - examinatrice
- Johanne Cohen, CNRS - examinatrice
- Arnaud Durand, Université Paris Cité - examinateur
- Philippe Schnoebelen, CNRS - examinateur
Encadrant·e·s :
- Patricia Bouyer-Decitre, CNRS
- Stéphane Le Roux, ENS Paris-Saclay