Positional games were introduced by Hales and Jewett in 1963, and their study became more popular when Erdős and Selfridge showed their connection to Ramsey theory and hypergraph coloring in 1973. Several conventions of these games exist, and the most popular one, Maker-Breaker was proved to be PSPACE-complete by Schaefer in 1978. The study of their complexity then stopped for decades, until 2017 when Bonnet, Jamain, and Saffidine proved that Maker-Breaker is W[1]-complete when parameterized by the number of moves. The study was then intensified when Rahman and Watson improved Schaefer’s result in 2021 by proving that the PSPACE-hardness holds for 6-uniform hypergraphs. More recently, Galliot, Gravier, and Sivignon proved that computing the winner on rank 3 hypergraphs is in P, and Keopke proved that the PSPACE-hardness also holds for 5-uniform hypergraphs. We focus here on the Client-Waiter and the Waiter-Client conventions. Both were proved to be NP-hard by Csernenszky, Martin, and Pluhár in 2011, but neither completeness nor positive results were known. In this paper, we complete the study of these conventions by proving that the former is PSPACE-complete, even restricted to 6-uniform hypergraphs, and by providing an FPT-algorithm for the latter, parameterized by the size of its largest edge. In particular, the winner of Waiter-Client can be computed in polynomial time in rank k hypergraphs for any fixed integer k. Finally, in search of the exact location of the complexity gap in the Client-Waiter convention, we focus on rank 3 hypergraphs. We provide an algorithm that runs in polynomial time with an oracle in NP.

In this paper, we introduce and study a new scoring game on graphs called smash and grab. In this game, two players, called Left and Right, take turns removing a vertex of the graph as well as all of its neighbours that become isolated by this removal. For each player and each of their turns, they score the number of vertices that were removed on their turn. The game ends when there are no more vertices remaining, and the player with the highest final score wins. We denote by Ls(G) the difference between Left and Right's final scores in G when Left starts and both players play optimally (they both aim to maximise their scores). We mainly study this parameter for different graph classes. We notably prove that Ls(F)≥0 for any forest F (i.e., the first player cannot lose). We then use this result to compute the exact value of Ls(G) for particular forests such as unions of paths and subdivided stars. The result in paths then solves the case of a unique cycle. Finally, we prove that, for a generalisation of the game, computing the score is PSPACE-complete.

Avoidance games are games in which two players claim vertices of a hypergraph and try to avoid some structures. These games have been studied since the introduction of the game of SIM in 1968, but only few complexity results have been found out about them. In 2001, Slany proved some partial results on Avoider-Avoider games complexity, and in 2017 Bonnet et al. proved that short Avoider-Enforcer games are Co-W[1]-hard. More recently, in 2022, Miltzow and Stojaković proved that these games are NP-hard. As these games correspond to the misère version of the well-known Maker-Breaker games, introduced in 1963 and proven PSPACE-complete in 1978, one could expect these games to be PSPACE-complete too, but the question has remained open since then. Here, we prove here that both Avoider-Avoider and Avoider-Enforcer conventions are PSPACE-complete. Using the PSPACE-hardness of Avoider-Enforcer, we provide in appendix proofs that some particular Avoider-Enforcer games also are.