Valentin Gledel (Univ. Umea, Suède)

Résumé

Les jeux positionnels sont des jeux à deux joueurs joués dans un hypergraphe. Les joueurs sélectionnent alternativement des sommets de l’hypergraphe et les conditions de victoires dépendent uniquement du remplissage des hyperarêtes. Le morpion est un exemple célèbre de jeu positionnel, les lignes, colonnes et diagonales formant les hyperarêtes et le premier joueur à remplir une hyperarête gagnant la partie. Les jeux positionnels sont étudiés depuis leur introduction par Hales et Jewett en 1963, puis popularisée par Erdős and Selfridge in 1973 et ont conservé jusqu’à aujourd’hui un vif intérêt.

Cependant, même si la convention Maker-Breaker, forme la plus étudiée des jeux positionnels, a été prouvée comme étant PSPACE-complet par Schaefer en 1978, beaucoup de problèmes restaient ouverts concernant la complexité des jeux positionnels. En particulier, la complexité de la convention Avoider-Enforcer restait ouverte et les jeux positionnels et leur complexité étaient peu considérée sur des classes plus restreintes d’hypergraphes. Cette présentation commencera par une introduction aux jeux positionnels avec un aperçu des résultats principaux du domaine. Puis, nous donnerons une ébauche de preuve pour la PSPACE-completude de la convention Avoider-Enforcer récemment prouvée. Enfin, nous complèterons cette présentation en étudiant les jeux positionnels en lien avec des problèmes de graphes et la complexité de tels problèmes.

Abstract

Positional games are two-player games played on a hypergraph. The players alternate selecting vertices of the hypergraph, and the winning conditions depend solely on the filling of the hyperedges. Tic-tac-toe is a famous example of a positional game, with the rows, columns, and diagonals forming the hyperedges and the first player to fill a hyperedge winning the game. Positional games have been studied since their introduction by Hales and Jewett in 1963, and were popularized by Erdős and Selfridge in 1973. They still remain of great interest today.

However, even though the Maker-Breaker convention, the most studied form of positional games, was proven to be PSPACE-complete by Schaefer in 1978, many problems remained open regarding the complexity of positional games. In particular, the complexity of the Avoider-Enforcer convention remained open, and positional games and their complexity were little considered on more restricted classes of hypergraphs. In this presentation, we will discuss recent advances in the study of the complexity of positional games, including new results on the Avoider-Enforcer convention and on positional games on restricted classes of hypergraphs. This presentation will begin with an introduction to positional games, providing an overview of the main results in the field. Then, we will give a proof sketch for the recently proven PSPACE-completeness of the Avoider-Enforcer game. Finally, we will conclude this presentation by studying positional games in relation to graph problems and the complexity of such problems.