Résumé :

On se place dans un graphe fini. Deux adversaires, Alice et Bob, prennent tour à tour le contrôle d'un sommet en respectant une règle simple. Le jeu s'arrête lorsque plus aucun nouveau sommet ne peut être contrôlé, soit parce qu'il ne reste plus de sommets libres, soit parce que la règle ne serait plus respectée.

Il existe plusieurs variantes pour les conditions de victoire ; dans tous les cas, les hypothèses que nous faisons permettent d'invoquer le célèbre théorème de Zermelo - von Neumann : Alice ou Bob a une stratégie gagnante. Mais qui d'Alice ou de Bob peut s'assurer la victoire ? Très souvent, cette question pose en fait un problème PSPACE-complet. C'est le cas pour les deux jeux dont je parlerai dans cet exposé. Cette difficulté invite à se restreindre à des variantes de règles plus contraignantes ou à des classes de graphes plus structurées.

J'exposerai des stratégies gagnantes pour Alice, découvertes en 2024 avec Nicolas Martins, Nicolas Nisse et Rudini Sampaio, pour le jeu de convexité asymétrique et pour le jeu de coloration dans les grilles finies.