Complexity of positional games
Time: 14:00 -- Location: LRI, 445
summary: 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.