The Avoider-Enforcer game on hypergraphs of rank 3

Florian Galliot, Valentin Gledel, Aline Parreau · 2025

Read The Avoider-Enforcer game on hypergraphs of rank 3 by Florian Galliot, Valentin Gledel, Aline Parreau (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-21672.txt.

Introduction

Florian Galliot, Valentin Gledel, and Aline Parreau analyze a two-player game played on the vertices of a hypergraph. Avoider and Enforcer claim vertices in turn. Enforcer wins if Avoider ends up owning every vertex of some edge; otherwise Avoider escapes.

The paper first develops general results about the game's outcome, including how disjoint unions of hypergraphs behave. It then settles who wins on all hypergraphs of rank two. For linear hypergraphs of rank three, the winner is determined when Avoider makes the last move. The structural characterizations behind these results also yield polynomial-time algorithms for deciding the winner. Such positional games connect combinatorics with strategy stealing and pairing arguments.

Catalog record

CREATORFlorian Galliot, Valentin Gledel, Aline Parreau
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-21672

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Avoider-Enforcer game on hypergraphs of rank 3 Thanks: This research was partly supported by the ANR project P-GASE (ANR-21-CE48-0001-01) Florian Galliot, Valentin Gledel, Aline Parreau Abstract In the Avoider-Enforcer convention of positional games, two players—Avoider and Enforcer—take turns selecting vertices from a hypergraph H H . Enforcer wins if, by the time all vertices of H H have been selected, Avoider has completely filled an edge of H H with her vertices; otherwise, Avoider wins. In this paper, we first give some general results, in particular regarding the outcome of the game and disjoint unions of hypergraphs. We then determine which player has a winning strategy for all hypergraphs of rank 2, and for linear hypergraphs of rank 3 when Avoider plays the last move. The structural characterisations we obtain yield polynomial-time algorithms. 1 Introduction Positional games have been introduced by Hales and Jewett [ 15 ] and popularised by Erdős and Selfridge [ 8 ] . The game board is a hypergraph H with vertex set V(H) and edge set E(H) . Two players take turns picking a previously unpicked vertex of the hypergraph. There are four main conventions for determining the winner. In strong games , both players have the same objective: in the Maker-Maker convention, whoever fills an edge (i.e. picks all its vertices) wins the game, whereas in the Avoider-Avoider convention, whoever first fills an edge loses the game. In weak games , the players’ objectives are complementary: in the Maker-Breaker convention, Maker aims at filling an edge while Breaker aims at preventing her from doing so, whereas in the Avoider-Enforcer convention, Avoider aims at avoiding filling an edge while Enforcer aims at forcing her to do so. The Maker-Maker and Maker-Breaker conventions characterise achievement games , whereas the Avoider-Avoider and Avoider-Enforcer conventions characterise avoidance games . Since all these conventions define finite two-player games with perfect information, either there exists a winning strategy for one of the players, or optimal play leads to a draw (this can only happen in strong games). The first convention to be introduced was the Maker-Maker convention [ 15 ] , which is the most natural one since it models the famous game of Tic-Tac-Toe. It can be noted, using a strategy-stealing argument [ 15 ] , that there are no situations where the players would rather pass their turn, and therefore either the first player has a winning strategy or optimal play leads to a draw. Apart from that, few general results are known, as this convention is hard to tackle. There is no monotonicity (adding edges may harm the first player), and it is not known how to compute a winning strategy for the first player on a disjoint union of two games given a winning strategy on each of them. These difficulties are mainly due to the fact that the players pursue two goals at once: filling an edge, and preventing the opponent to fill one first. This is the reason why the Maker-Breaker convention was introduced by Chvátal and Erdős [ 6 ] . Constructive results are generally easier to achieve compared to the Maker-Maker convention: for instance, it is very easy to design optimal strategies on a disjoint union of two games from optimal strategies on each separate game. These games are monotonous, since adding an edge can clearly only benefit Maker. Some other general results are known, such as the “Erdös-Selfridge criterion” or “pairing strategies” which give sufficient conditions for Breaker to have a winning strategy. The Maker-Breaker convention is actually by far the most studied (see for example the books [ 2 , 16 ] ). Maker-Breaker games on hypergraphs of small rank have been much investigated. Hypergraphs of rank at most 2 are trivially solved. Hypergraphs of rank 3 were first studied in the linear case (i.e. when any two edges share at most one vertex) by Kutz, who obtained a polynomial-time algorithm to decide which player has a winning strategy [ 20 ] . This result has been recently extended to all hypergraphs of rank 3 by Galliot, Gravier and Sivignon [ 11 ] . On the other hand, it has been known since 1978 that deciding the winner of a Maker-Breaker game is PSPACE-complete even if the edges have size 11 [ 25 ] . This result has since then been improved to edges of size 6 [ 24 ] and very recently to edges of size 5 [ 19 ] . The other two conventions, which revolve around avoiding filling an edge, have received less attention but are now being increasingly studied [ 3 , 12 , 22 , 26 ] . The way in which avoidance games are played is quite different. Indeed, in these conventions, players would often rather pass than pick a vertex. As a consequence, there are cases where the second player has a winning stragegy. All in all, methods used for achievement games mostly do not transfer to avoidance games. As an illustration, it took until 2023 to prove that deciding which player has a winning strategy is PSPACE-complete for the Avoider-Enforcer convention, over 40 years later than for the Maker-Breaker convention. Among the two avoidance conventions, Avoider-Avoider games, being strong games, present a similar predicament as Maker-Maker games. Deciding which player (if any) has a winning strategy on a hypergraph of rank 2 is already PSPACE-complete in this convention [ 9 ] . This paper focuses on the Avoider-Enforcer convention, which owes its first general formulation to Lu [ 21 ] . Since this is a weak convention i.e. the two players have complementary goals, one can hope that these games satisfy some convenient general properties, similar to those of Maker-Breaker games (despite the differences in the way these games are played). For example, it is already known that the Erdös-Selfridge criterion can be adapted to the Avoider-Enfocer convention [ 18 ] . Furthermore, pairing strategies have been used to prove the PSPACE-completeness of Avoider-Enforcer games [ 12 , Lemma 6] . That last paper illustrates how complexity proofs for Maker-Breaker games can often be adapted to Avoider- Enforcer games. Beside these works, the Avoider-Enforcer convention seems to have been studied mostly for specific games [ 1 , 3 , 7 , 13 ] and not for general hypergraphs, except those with pairwise-disjoint edges which are entirely solved [ 10 ] . Our contribution. The aim of this paper is to give general properties of Avoider-Enforcer games and study this convention in hypergraphs of small rank. An important property that we establish is that, in contrast with the Maker-Breaker convention, the relevant distinction to make when studying Avoider-Enforcer games is based on who plays the last move of the game (when all vertices are picked) rather than who plays the first move. Indeed, any player that has a winning strategy playing last also has a winning strategy playing second-to-last. This result leads us to define the outcome of a hypergraph as the identity of the player that has a winning strategy in each case (Avoider playing last or Enforcer playing last). We then show that the outcome of a disjoint union of games is uniquely determined by the outcomes of its components.

Read the complete text