# Poset Positional Games *

Guillaume Bagan, Eric Duchêne, Florian Galliot, Valentin Gledel, Mirjana

Mikalački, Nacim Oijid, Aline Parreau, Miloš Stojaković

► To cite this version:

Guillaume Bagan, Eric Duchêne, Florian Galliot, Valentin Gledel, Mirjana Mikalački, et al.. Poset Positional Games *. 12th International Conference on Fun with Algorithms (FUN 2024), Jun 2024, La maddalena, Italy. hal-05390315

HAL Id: hal-05390315

https://hal.science/hal-05390315v1

Submitted on 1 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Poset Positional Games*

Guillaume Bagan¹, Eric Duchêne¹, Florian Galliot², Valentin Gledel³, Mirjana Mikalački†⁴,
Nacim Oijid¹, Aline Parreau¹, and Miloš Stojaković†⁴

¹Univ Lyon, CNRS, UCBL, INSA Lyon, LIRIS, UMR5205, F-69622 Villeurbanne, France

²Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France

³Université Savoie Mont Blanc, CNRS UMR5127, LAMA, Chambéry, F-73000, France

⁴Department of Mathematics and Informatics, Faculty of Sciences, University of Novi Sad, Serbia

## Abstract

We propose a generalization of positional games, supplementing them with a restriction on the order in which the elements of the board are allowed to be claimed. We introduce poset positional games, which are positional games with an additional structure – a poset on the elements of the board. Throughout the game play, based on this poset and the set of the board elements that are claimed up to that point, we reduce the set of available moves for the player whose turn it is – an element of the board can only be claimed if all the smaller elements in the poset are already claimed.

We proceed to analyze these games in more detail, with a prime focus on the most studied convention, the Maker-Breaker games. First we build a general framework around poset positional games. Then, we perform a comprehensive study of the complexity of determining the game outcome, conditioned on the structure of the family of winning sets on the one side and the structure of the poset on the other.

# 1 Introduction

## 1.1 General motivation

**Positional games.** Positional games are a class of combinatorial games that have been extensively studied in recent literature – see books [5] and [11] for an overview of the field. They include popular recreational games like Tic-Tac-Toe, Hex and Sim. Structurally, a positional game is a pair $(X, \mathcal{F})$, where $X$ is a (finite) set that we call the board, and $\mathcal{F} \subseteq 2^X$ is a collection of sets that we call the winning sets. The pair $(X, \mathcal{F})$ is referred to as the hypergraph of the game. The game is played in the following way: two players alternately claim unclaimed elements of the board, until all the elements are claimed. There are several standard conventions, defining the way the winner is determined: Maker-Maker games, Maker-Breaker games, Avoider-Enforcer games, etc.

In *Maker-Maker games*, also known as strong making games, players compete to fill up one of the winning sets i.e. claim all its elements, and whoever does it first wins. If there is no winner by the time all the board elements are claimed, the game is declared a draw. Tic-Tac-Toe ("3-in-a-line") is a notable representative of this type of games and every child knows the game ends in a draw, provided that both players play optimally. It can be generalized to the $n \times n$ board, going under

<footnote>*This research was partly supported by the ANR project P-GASE (ANR-21-CE48-0001-01).</footnote>

<footnote>†Partly supported by Provincial Secretariat for Higher Education and Scientific Research, Province of Vojvodina (Grant No. 142-451-2686/2021). Partly supported by Ministry of Science, Technological Development and Innovation of Republic of Serbia (Grants 451-03-66/2024-03/200125 & 451-03-65/2024-03/200125).</footnote>
the name “n-in-a-line”, and it is also known to be a drawn game [5] for all $n \ge 3$. More generally, Tic-Tac-Toe can be played on the hypercube $[n]^d$, where the winning sets are all the geometric lines of cardinality $n$. The Hales-Jewett Theorem [10] states that, for every $n$, there exists a positive number $d$, also called the Hales-Jewett number $HJ(n)$, such that for all $k \ge d$, the game $[n]^k$ is a first player win.

Generally speaking, the strong making games are natural to introduce and study, and many recreational games are of this type. Hence, it is no wonder that numerous questions about them have been asked in the literature. Yet, it may come as a surprise that the majority of those questions remain unanswered. The thing is, in a typical strong making game, each player's goal can be seen as two-fold: they are simultaneously trying to claim a winning set and to block their opponent's attempts at claiming a winning set. This makes most such games notoriously hard to analyze, and hardly any general tools are known for this purpose. As a consequence, there are very few published results about this convention, when compared to Maker-Breaker games.

In *Maker-Breaker games*, we call the players Maker and Breaker, and they have different goals – Maker wins if she fills up a winning set, while Breaker wins otherwise, i.e. if he claims at least one element in each winning set. Note that no draw is possible in this convention. Maker-Breaker games are the most researched convention of positional games, ever since Erdős and Selfridge [8] first introduced them in 1973. Looking at Tic-Tac-Toe on the standard 3×3 board in the Maker-Breaker convention, it is straightforward to convince oneself that Makers wins when playing first.

The main problem on positional games consists in determining the *outcome* i.e. the identity of the player who has a winning strategy (possibly depending on who starts), if there is one, assuming that both players are playing optimally. The study of the complexity of computing the outcome of a given positional game can be traced back to Schaefer [14], who was first to prove that Maker-Breaker games are PSPACE-complete, even when the winning sets are of size at most 11. This was later improved by Rahman and Watson [13], requiring only winning sets of size 6. On the other hand, Galliot et al. [9] proved that the outcome of any Maker-Breaker game with winning sets of size at most 3 can be determined in polynomial time. Maker-Maker games are also known to be PSPACE-complete, as shown by Byskov in [6].

**Poset positional games.** Let us now take a closer look at a popular recreational game, Connect-4, which has a lot in common with the Tic-Tac-Toe family of positional games. In Connect-4, two players play on a board that is 7-wide and 6-high. They move alternately by placing a token of theirs in a column of their choice. Each placed token drops down with “gravity”, landing on top of the last previously placed token in that column, or heading all the way to the bottom of the column if it is empty. The first player with tokens on four consecutive positions in a line (vertical, horizontal or diagonal) wins, and, if neither of the players manages to do that by the time all the columns are full, then a draw is declared. Although the game is similar to Tic-Tac-Toe at first glance, there is one crucial difference – the players cannot choose freely from all the empty positions of the board, as at any point a column offers at most one available position (the lowest token-free position).

The outcome of the game is known as a first player win, as shown by Allis in [3], and independently by Allen [1] who later wrote a whole book [2] about this game. Connect-4 was solved in [17] for some nonstandard board sizes, and for some others in [16].

Recently, Avadhanam and Jena [4] studied *Connect-Tac-Toe*, where they introduce a restriction on which unclaimed elements can be claimed, combining the nature of Connect-4 with the positional game of Tic-Tac-Toe. They also look at the generalized $[n]^d$ Connect-Tac-Toe, played on a hypercube $[n]^d$, relating it to the restricted version of the $[n]^d$ Tic-Tac-Toe. Additionally, they give a lower bound on an analogue of the Hales-Jewett number, $HJ(n)$, in this setting.

In the present paper, we propose a new framework which, in full generality, enables us to combine
the move restrictions with positional games (like it is done in Connect-4). Namely, we introduce *poset positional games*, which are positional games with an additional structure – a poset on the elements of the board. Throughout the game play, based on this poset and the set of elements that are claimed up to that point, we reduce the set of available moves for the player whose turn it is – an element of the board can only be claimed if all the smaller elements (in the poset) are already claimed.

We proceed to analyze these games in more detail, with a prime focus on the most studied convention, the Maker-Breaker games. After setting out a formal introduction of poset positional games, we go on to build a general framework around them. Then, we perform a comprehensive study of the complexity of determining the game outcome, conditioned on the structure of the family of winning sets on the one side and the structure of the poset on the other.

## 1.2 Framework of poset positional games

A poset $P$ on a set $X$ is defined by a partial order relation $\leq$. On top of that, we use $<$ to denote the same relation acting on distinct elements. In this paper, posets will be depicted by directed graphs in the usual way, where the elements are vertices, and two elements $x$ and $y$ satisfy $x \leq y$ if and only if there exists a directed path from $x$ to $y$. Two elements are deemed *incomparable* if there exists no directed path between them.

In addition, we will use the following standard definitions about posets. A *chain* is a set of elements that are pairwise comparable. An *antichain* is a set of elements that are pairwise incomparable. The *height* of a poset is the cardinality of its longest chain. The *width* of a poset is the cardinality of its largest antichain. Given an element $x$, we say that $y$ is a *predecessor* (resp. a *successor*) of $x$ if $y < x$ (resp. $x < y$) and there is no other element between $x$ and $y$. An element $x$ is said to be *maximal* (resp. *minimal*) in the poset if it has no successor (resp. no predecessor).

We are now able to formally define a poset positional game as follows. A *poset positional game* is a triple $(X, \mathcal{F}, P)$ where $X$ is a finite set of elements (also called *vertices*), $\mathcal{F}$ is a collection of subsets of $X$ corresponding to the *winning sets*, and $P$ is a poset on $X$.

The game is played by two players that alternately claim an unclaimed vertex $x$ of $X$ such that all vertices smaller than $x$ have already been claimed. The rest stays the same as before. In the Maker-Maker convention, the first player that fills up a winning set $S \in \mathcal{F}$ wins. If no player manages to fill up a winning set, the game ends in a draw. In the Maker-Breaker convention, Maker wins if she fills up a winning set at some point during the game, otherwise Breaker wins. During a game, when a player claims a single vertex, we call that a *move*, whereas a *round* corresponds to a pair of moves made successively by both players.

Note that a standard positional game is a poset positional game where all the vertices are pairwise incomparable. Furthermore, in poset positional games, from any given position, the set of moves that are available to the next player forms an antichain of the poset. In particular, there are at most $w$ available moves at any point of a game, where $w$ is the width of the poset.

It is a well-known result that, for any standard positional game played in the Maker-Maker convention, the second player cannot have a winning strategy, so that the only possible outcomes are a first player win $\mathcal{FP}$ or a draw $\mathcal{D}$. Similarly, for any standard positional game played in the Maker-Breaker convention, there are only three possible outcomes (if we do not specify who starts):

* $\mathcal{M}$ if Maker has a winning strategy no matter who starts the game,

* $\mathcal{B}$ if Breaker has a winning strategy no matter who starts the game,

* $\mathcal{N}$ if the next player (i.e. the player whose turn it is) has a winning strategy.

When switching to the framework of poset positional games, the property asserting that the second
player never wins is not true any more. As a consequence, there are game positions for which the
next player may have interest in skipping their turn. The corresponding outcome will be denoted
by $\mathcal{P}$ (standing for “dPrevious player wins”, or equivalently meaning that the second player has a
winning strategy). Such phenomena are generally called *zugzwangs* in the literature of combinatorial
games [7].

From now on, unless explicitly stated, we will only consider the Maker-Breaker convention of poset
positional games. Though the computation of the outcome is generally the main issue when investi-
gating such games, this study can, under certain circumstances, be reduced to the case of a particular
player starting the game. Indeed, starting with a game $\mathcal{G} = (X, \mathcal{F}, P)$ where Maker (resp. Breaker)
is the first player and claims a vertex $x$, we get a resulting game $\mathcal{G}' = (X', \mathcal{F}', P')$ where Breaker
 resp. Maker) is the first player, defined by $X' = X - x$, $P' = P - x$ and $\mathcal{F}' = \{W \setminus \{x\} | W \in \mathcal{F}\}$
 (resp. $\mathcal{F}' = \{W | W \in \mathcal{F}, x \notin W\}$). Therefore, when studying a class of games which is stable
 under Maker's (resp. Breaker's) moves in terms of that update, we may freely assume that Breaker
 (resp. Maker) is the first player, up to considering all possibilities for their opponent's first move
 otherwise. In this paper, all studied classes will be stable under Breaker's moves, so we will al-
 ways assume that Maker is the first player. Therefore, the decision problem that will be mainly
 investigated is the following:

## MB POSET POSITIONAL GAME

**Input:** A poset positional game $\mathcal{G} = (X, \mathcal{F}, P)$.

**Output:** The player having a winning strategy (i.e. Maker or Breaker) when Maker starts.

Since standard positional games are included in poset positional games, the problem MB POSET POSITIONAL GAME is PSPACE-complete from a result of Schaefer [14].

## 1.3 Exposition of the results

The main objective of this paper is to consider the complexity of MB POSET POSITIONAL GAME related to some parameters of the instance. More precisely, we have chosen to focus on the properties of the poset, as it is the main distinctiveness of the current contribution, comparing the results we obtain to the previous results about standard positional games. In Section 2, we will firstly examine the problem depending on the height of the poset. As it is already known that, even for height 1 (i.e. all the elements are pairwise incomparable) and winning sets of size 6, the problem is PSPACE-complete [13], we will also refine our classification according to the number and/or the size of the winning sets. The main contribution of this section addresses the case where there is only one winning set of size 1. By adding such a condition, the problem admits a complexity jump between instances of height 2, proved to be polynomial, and height 3, proved to be NP-hard.

Section 3 deals with the width of the poset. As the case of width 1 is straightforward (P is made of only one chain, so the order of the moves is completely predetermined), we start by considering instances with width 2. We show that MB POSET POSITIONAL GAME is PSPACE-hard in this case, even if all the winning sets are of size 3. This illustrates a major difference with standard positional games, which are known to be tractable in this setting. We then give a polynomial-time algorithm that solves the general case where the width of the poset and the number of winning sets are fixed.

Section 4 is devoted to the case where the poset is a union of disjoint chains. This case is a direct generalization of the game Connect-4. Our first result is a full characterization of the outcome when all the winning sets are of size 1. When the winning sets are of size at most 2, things are more tricky, but we do provide a polynomial-time algorithm when the width of the poset (i.e. the number of chains in the union) is fixed. Finally, by adding the restriction that the height of each chain is at most 2, we get a polynomial-time algorithm regardless of the number of chains.
Table 1 summarizes all the results known about the complexity of MB POSET POSITIONAL GAME, referring either to the literature of standard positional games, or to results proved in the current paper. In the table, recall that the complexity class XP defines the class of problems parameterized by a parameter *k* and that can be solved in time $O(|X|^{f(k)})$, where $|X|$ is the size of the instance and *f* is a computable function.

In order to satisfy the constraints of the submission, note that a large part of our results do not have a complete proof in the first ten pages of this paper. For most of them, we provide a sketch of the proof, and full proofs are given in Appendix. In addition, the choice of considering the Maker-Breaker convention instead of the Maker-Maker one is reinforced in Appendix by Theorem 18, which yields an instance (height 2 and all nonminimal elements are winning sets of size 1) for which the resolution is PSPACE-complete in the Maker-Maker convention, whereas it is in polynomial time in the Maker-Breaker convention (see Theorem 4).

<table><caption>Table 1: Complexity of MB POSET POSITIONAL GAME depending on some parameters of the poset and of the collection of winning sets.</caption><thead><tr><th>winning sets</th><th>general</th><th>height h</th><th>width w</th><th>disjoint chains</th></tr></thead><tbody><tr><th>general</th><td>PSPACE-c [13]</td><td>h = 1:<br>PSPACE-c [13]</td><td>w = 1: P<br>w = 2:<br>PSPACE-c<br>(Th. 7)</td><td>h = 1:<br>PSPACE-c [13]</td></tr><tr><th>size s</th><td>s = 3:<br>PSPACE-c<br>(Th. 7)</td><td>h = 1, s = 6:<br>PSPACE-c [13]<br>h = 2, s = 3:<br>NP-h (Th. 5)</td><td>w = 2, s = 3:<br>PSPACE-c<br>(Th. 7)</td><td>s = 1:<br>P (Th. 11)<br>s = 2:<br>XP by w (Th. 14)<br>h = 2, s = 2:<br>P (Th. 15)</td></tr><tr><th>number m</th><td>NP-hard<br>(Th. 6)</td><td>m = 1, h = 3:<br>NP-hard (Th. 6)</td><td>XP (Th. 8)</td><td>m = 1:<br>P (Th. 11<br>and Remark 1)</td></tr><tr><th>number m<br>and size s</th><td>m = 1, s = 1:<br>NP-hard<br>(Th. 6)</td><td>h = 2, m = 1, s = 1:<br>P (Th. 3)<br>h = 3, m = 1, s = 1:<br>NP-hard (Th. 6)</td><td>XP (Th. 8)</td><td>XP (Th. 8)</td></tr></tbody></table>

# 2 Posets of small height

## 2.1 Posets of height 2

We first look at what happens when all the winning sets are of size 1. This case is rarely straight-forward, and often deserves to be studied depending on some parameters of the poset. In addition, it is closely correlated to the case where there is a unique winning set (of any size). The following remark explains the link between both situations.

**Remark 1.** Up to switching the roles of the players, a poset positional game with a single winning
set of size *k* is equivalent to a poset positional game with *k* winning sets of size 1.

In the above remark, the equivalence means that the two games have the same outcome. Indeed, Maker wins when there is a single winning set of size *k* if and only if she manages to claim all the elements of this set. In the second game, a win of Breaker consists in claiming all the winning sets (of size 1), thus corresponding to the equivalence. Note that Breaker is starting in one of the two games, but this is not a pitfall since both these classes are stable under Breaker's moves.

We continue with a minor result which is useful when dealing with winning sets of size 1. Given a poset *P* and a vertex *x*, we denote by *p*(*x*) the number of vertices that are not greater or equal to *x* i.e. *p*(*x*) := |*X*| - |{*y* | *y* ≥ *x*}|. This quantity is used in the following lemma, which yields a necessary and sufficient condition for Maker to win when there is a unique winning set of size 1.

**Lemma 2.** Let $\mathcal{G} = (X, \{{\{x}\}}, P)$ be a poset positional game. Suppose that, after some rounds of play in $\mathcal{G}$, all predecessors of $x$ have been claimed apart from one, which we denote by $y$. Then, in this position, Maker wins if and only if $p(y)$ is odd.

**Theorem 3.** MB POSET POSITIONAL GAME can be solved in polynomial time when: the poset is of height 2, there is only one winning set, and this winning set is of size 1.

*Sketch of the proof.* Let $\{x\}$ be the winning set. We partition the predecessors of $x$ into two sets $M$ and $B$, where $M$ (resp. $B$) contains the predecessors of $x$ such that $p(y)$ is even (resp. odd). Then Maker wins if and only if $|M| \le |B|$. □

The situation is already much more complicated with two winning sets of size 1 – we leave this as an open problem. However, for winning sets of size 1 and a poset of height 2 whose nonminimal elements are all winning sets, one can compute the outcome in polynomial time, as we now show. Note that the same situation is PSPACE-complete in the Maker-Maker convention (see Theorem 18 in Appendix).

**Theorem 4.** MB POSET POSITIONAL GAME can be solved in polynomial time when: the poset is of height 2, all the winning sets are of size 1, and all nonminimal elements are winning sets.

*Sketch of the proof.* Let $P$ be a poset of height 2 on a set $X$. We say the minimal elements of $P$ are the “bottom” vertices, and the others are the “top” vertices. We say that $x$ is a *private predecessor* of $y$ if $y$ is the only successor of $x$.

The poset positional game we consider is $\mathcal{G} = (X, \{{\{y}\}, y \text{ top vertex}\}, P)$. We prove that Maker wins if and only if (1) $|X|$ is odd or (2) there exists a top vertex $y$ which does not have more private predecessors than non-private ones.

If (1) holds then, since Maker starts, she also plays last, which means she can win by waiting for Breaker to claim the last predecessor of some top vertex. If (2) holds, then Maker can ensure that all the private predecessors of $y$ are claimed before all the non-private ones are, after which she waits for Breaker to claim the last predecessor of $y$. She might have to claim it herself, but that will make at least two top vertices available at once, meaning she will win with her next move.

If none of the conditions hold, then Breaker can maintain the property that “all the top vertices have strictly more private predecessors than non-private ones” during the game. This allows Breaker to claim all the top vertices, meaning he wins. □

For posets of height $h = 2$, as the size $s$ of the winning sets increases, the value $s = 3$ is the smallest one for which we have identified an algorithmic complexity jump.

**Theorem 5.** MB POSET POSITIONAL GAME is NP-hard, even when restricted to instances where the poset has height 2 and all the winning sets are of size 3.
<figure><img src="image_2.png" /><figcaption>Figure 1: The poset positional game obtained by reduction of $\forall x_1 \exists x_2 \forall x_3 \exists x_4 (x_1 \lor x_2 \lor x_3) \land (\neg x_2 \lor x_3 \lor \neg x_4)$</figcaption></figure>

*Sketch of the proof.* The proof is a reduction from 3-SAT. Let $\phi$ be a 3-SAT formula. We build a poset positional game $\mathcal{G} = (X, \mathcal{F}, P)$ with $P$ of height 2 and winning sets of size 3 as follows:

* For any variable $x_i$ of $\phi$, we add four vertices $u_i, v_i, \overline{v_i}$ and $\tilde{v}_i$ in $X$.

* For any clause $C_j = l_{j1} \lor l_{j2} \lor l_{j3}$ in $\phi$, we add the winning set $S_j$ with, for $1 \le k \le 3$, $v_{jk} \in S_j$ if $l_{jk} = x_{jk}$, and $\overline{v}_{jk} \in S_j$ if $l_{jk} = \neg x_{jk}$.

* For any variable $x_i$ of $\phi$, we add the relations $u_i < v_i, u_i < \overline{v_i}$ and $u_i < \tilde{v}_i$ in $P$.

We prove that $\phi$ is satisfiable if and only if Breaker has a winning strategy in $\mathcal{G}$. $\square$

<figure><img src="image_3.png" /></figure>

## 2.2 Posets of height 3

We now consider posets of height 3. Using Lemma 2, we prove that MB POSET POSITIONAL GAME is NP-hard even if there is only one winning set and that winning set is of size 1. The reduction is done from the problem SET COVER.

**Theorem 6.** MB POSET POSITIONAL GAME is NP-hard even when restricted to instances where the poset has height 3, there is only one winning set, and that winning set is of size 1.

## 3 Posets of bounded width

In this section, we consider posets of bounded width. For width 1, all moves are forced, so the outcome is obviously computed in polynomial time. However, for width 2, we prove that MB POSET POSITIONAL GAME is already PSPACE-hard even if the winning sets are of size 3.

**Theorem 7.** MB POSET POSITIONAL GAME is PSPACE-complete even when restricted to instances where the poset is of width 2 and the winning sets are of size 3.

*Sketch of the proof.* The reduction is done from 3-QBF, which has been proved PSPACE-complete by Stockmeyer and Meyer [15]. In 3-QBF, the input is a formula of the form $\psi = \forall x_1 \exists x_2 \dots \forall x_{2n-1} \exists x_{2n} \phi(x_1, \dots, x_{2n})$ where $\phi$ is a 3-CNF formula. The output is the truth value of $\psi$. We build a poset positional game $\mathcal{G} = (X, \mathcal{F}, P)$ as follows:

* For any $1 \le i \le 2n$, we add two vertices $v_i$ and $\overline{v_i}$ in $X$.

* For any $1 \le i \le 2n - 1$, we also add a vertex $u_i$.

* For any clause $C_j = l_{j1} \lor l_{j2} \lor l_{j3}$ in $\phi$, we add a winning set $S_j \in \mathcal{F}$. For $1 \le k \le 3$, we have $v_{jk} \in S_j$ if $l_{jk} = x_{jk}$ and $\overline{v}_{jk} \in S_j$ if $l_{jk} = \neg x_{jk}$.

* For any $1 \le i \le 2n - 1$, we add in $P$ the relations $v_i < u_i, \overline{v}_i < u_i, u_i < v_{i+1}$ and $u_i < \overline{v}_{i+1}$.

See Figure 1 for an example. One can prove that $\psi$ is True if and only if Breaker wins in $\mathcal{G}$. $\square$

<figure><img src="image_4.png" /></figure>
If the number of winning sets is also bounded (by $m$), we give an algorithm running in time $O(|X|^{w2^m w^4})$.

**Theorem 8.** MB POSET POSITIONAL GAME can be decided in time $O(|X|^{w2^m w^4})$ for instances where the poset is of width at most $w$ and there are at most $m$ winning sets.

*Sketch of the proof.* The proof uses a dynamic approach. We characterize the games that can be reached from a game played on $G = (X, \mathcal{F}, P)$ using an antichain $Y$ of $X$, that represents the current available moves, and a boolean vector $B = (b_1, ..., b_m) \in \{0,1\}^m$ that represents, for each winning set, if Maker has claimed all its elements below $Y$ (and thus can still hope to claim it entirely). $\square$

# 4 Posets made of pairwise disjoint chains

In this section, motivated by the game Connect-4, we consider posets made of pairwise disjoint chains. In the rest of this section, we give positive results for poset positional games on pairwise disjoint chains with very small winning sets (but an unbounded number of them). We will often use parity arguments when discussing games on posets made of pairwise disjoint chains. Therefore, we introduce the following framework, which will be useful in this section. Consider a poset positional game $G = (X, \mathcal{F}, P)$ where $P$ is made of pairwise disjoint chains $C_1, ..., C_w$. The elements of the chain $C_i$ are denoted as $x_{i,1} > x_{i,2} > ... > x_{i,\ell_i}$. This numbering of the vertices from top to bottom is best adapted to define the following coloring: a vertex $x_{i,j}$ is colored white if $j$ has same parity as $|X|$, otherwise it is colored black.

## 4.1 Winning sets of size 1

The next two lemmas give sufficient conditions for Maker to win under particular conditions that are based on the above coloring. They can be proved with simple parity arguments. Combined together in the next theorem, they allow to have a complete characterization of the general case where all the winning sets are of size 1.

**Lemma 9.** If $\{u\} \in \mathcal{F}$ for some white vertex $u$, then Maker wins.

**Lemma 10.** If $|X|$ is odd and $\{u\}, \{v\} \in \mathcal{F}$ for some black vertices $u$ and $v$ sitting on different chains, then Maker wins.

**Theorem 11.** Let $G = (X, \mathcal{F}, P)$ be a poset positional game where $P$ is made of pairwise disjoint chains and all elements of $\mathcal{F}$ are of size 1. Maker wins $G$ if and only if at least one of the following conditions hold:

* there is a winning set that is a minimal element; or

* there is a white winning set; or

* $|X|$ is odd and there are two black winning sets on different chains.

In particular, MB POSET POSITIONAL GAME can be solved in linear time for such games.

*Sketch of the proof.* The “only if” direction is the one that remains to be proved. For even $|X|$, we show that Breaker can claim all the nonminimal black vertices. For odd $|X|$, we show that Breaker can claim all the nonminimal black vertices of any given chain. $\square$

Using this result, we can solve a basic case of $w \times h$ Connect-$k$ in Maker-Breaker convention, which is the poset positional game played on $w$ chains of height $h$ where the winning sets are the alignments of $k$ consecutive vertices (horizontal, vertical or diagonal). Note that the game is easily solved if $k \le 2$, or if $k > w$, or if $k > h$ and $wh$ is even.

**Corollary 12.** Let $k, w, h$ be integers with $3 \le k \le w$ and $h > 1$. If $w$ and $h$ are both odd, then Maker wins the $w \times h$ Connect-$k$ game in Maker-Breaker convention.
## 4.2 Winning sets of size at most 2

Things become more complicated when the winning sets are not all of size 1. In the presence of a black winning set of size 1, we can simplify the game. Using the same notations as before, assume that there exists a winning set {$x_{i,j}$} for some nonminimal black vertex $x_{i,j}$ with $j \ge 3$. We define a reduced game $G' = (X', \mathcal{F}', P')$ as follows.

If $|X|$ is even, then define $Y = \{x_{i_1}, \dots, x_{i,j-1}\}$, otherwise define $Y = \{x_{i_1}, \dots, x_{i,j-2}\}$. In both cases, let $X' = X \setminus Y$ and let $P'$ be the poset induced by $P$ on $X'$. Note that, since $x_{i,j}$ is black, we have removed an even number of vertices in both cases. In particular, the coloring of the vertices is the same for $(X', P')$ as for $(X, P)$. We now define the winning sets of $G'$ as follows. Let $S \in \mathcal{F}$. If $S \subseteq X'$, then $S \in \mathcal{F}'$. If $S$ only intersects $Y$ on white vertices, then $S \cap X' \in \mathcal{F}'$. Otherwise, i.e. if $S$ contains a black vertex greater than $x_{i,j}$, then we ignore $S$. See Figure 2 for an illustration in the case where $|X|$ is odd.

<figure><img src="image_5.png" /><figcaption>Figure 2: Reduction of a game $G$ containing a black winning set of size 1 to a game $G'$. The winning set $\{x_{1,4}, x_{2,2}\}$ disappears since it contains a black vertex in $Y$. The winning set $\{x_{1,3}, x_{2,3}\}$ becomes the winning set $\{x_{2,3}\}$ in $G'$ since $x_{1,3}$ is white. By Lemma 13, the two games have the same outcome. In this case, since $G'$ has a white winning set of size 1, both games are winning for Maker.</figcaption></figure>

**Lemma 13.** Assume that $G$ has no winning set containing only white vertices that are greater than $x_{i,j}$. Then the two games $G$ and $G'$ have the same outcome when Maker starts.

*Sketch of the proof.* We prove that, if a player has a winning strategy in $G'$, then that player has also a winning strategy in $G$. The idea is the same for both players: they follow their strategy on $G'$, as long as possible. When $x_{i,j}$ is claimed (by Breaker, otherwise Maker wins immediately), Maker can ensure to claim all the white vertices above $x_{i,j}$, thus completing a winning set she would have filled up in $G'$. If she cannot fill up a winning set of $G'$ (i.e. if Breaker wins $G'$), then Breaker can claim all the black vertices above $x_{i,j}$ and thus claim a vertex in all the winning sets of $G$. $\square$

Now equipped with this reduction, we can provide an algorithm when all the winning sets have size at most 2. Our algorithm is based on a dynamic programming approach. Thanks to Lemmas 9 and 13, we can reduce the number of sub-positions to consider. Indeed, we can assume that each chain contains at most one (black) winning set of size 1. Our algorithm dynamically computes the outcome of all these “useful” positions.

**Theorem 14.** MB POSET POSITIONAL GAME can be solved in time $O(h^{2(w+1)})$ for instances where the poset consists of w pairwise disjoint chains of height at most h and all winning sets have size
## 4.3 Winning sets of size at most 2, chains of height at most 2

The algorithm from Theorem 14 is not efficient for posets of unbounded width. However, when restricting the problem to posets of height at most 2, we do get a polynomial-time algorithm in this case also. Since the chains are of height at most 2, we will simply use the “top/bottom” terminology already adopted in the proof of Theorem 4, rather than the coloring previously used in this section.

**Theorem 15.** MB POSET POSITIONAL GAME can be solved in time $O(|X|^4)$ for instances where the poset on $X$ consists of pairwise disjoint chains of height at most 2 and all winning sets are of size at most 2.

*Sketch of the proof.* Let $x_1, \dots, x_t, y_1, \dots, y_t$ be the vertices of the chains of height 2, with $x_i < y_i$ for all $1 \le i \le t$. Let $x_{t+1}, \dots, x_w$ be the other vertices if there are any. We say the $x_i$ are the “bottom” vertices and the $y_j$ are the “top” vertices. The proof distinguishes two cases depending on the parity of $|X|$. When $|X|$ is odd, there are several possibilities, but each of them is a straightforward win for one of the two players. When $|X|$ is even, the situation is more tricky. In that case, the key argument is based on two reductions R1 and R2 that preserve the outcome:

R1: Assume there exists a winning set of the form $\{x_i, x_j\}$ that is disjoint from all the other winning sets. Then remove $x_i$ and $x_j$.

R2: Assume there exists a nonempty set of indices $I \subseteq \{1, \dots, t\}$ such that all the winning sets that contain some $x_i$ with $i \in I$ also contain some $y_j$ with $j \in I$. Then remove all the vertices with indices in $I$. $\square$

# 5 Conclusion and future work

The current work introduces a new framework that opens the door to a variety of perspectives. Our analysis with respect to the parameters of the poset led to a first classification of the complexity of MB POSET POSITIONAL GAME, which is a step towards a better understanding of the boundary between tractability and hardness. The results presented here directly induce a list of open problems that arise naturally in order to refine this boundary. Among them, we have identified the following two questions that seem the most relevant for us:

* When there is exactly one winning set of size 1, the height of the poset makes a difference between tractability ($h=2$) and NP-hardness ($h=3$). Therefore, when $h=2$, it is worthwhile to examine how the conditions on the number $m$ of winning sets and their size $s$ impact the algorithmic complexity. A next study would be to investigate the case $m=2$ and $s=1$.

* In the case of disjoint chains, an analysis of the complexity according to their width (i.e. the number of chains) is a natural perspective. In particular, one may focus on the case $w=2$, even when restricted to $s \le 3$ (since we have a polynomial-time algorithm for $s=2$). It would also be interesting to obtain a hardness results for disjoint chains.

Going back to our initial motivation of giving a general framework for Connect-k games, one could also examine the case of boards of even size for this game. For example, the famous case $(k, w, h) = (4, 7, 6)$, is known to be a Maker win in the Maker-Breaker convention since it a first player win in the Maker-Maker convention. However, a direct proof for the Maker-Breaker convention could be considered, that could also be extended to other sizes.

Finally, while we mostly studied the poset positional games in the Maker-Breaker convention, our definition can be transposed to all other conventions of positional games. It would therefore be interesting to perform a similar analysis for Maker-Maker or Avoider-Enforcer poset positional games.
## References

[1] James D. Allen. Expert play in Connect-Four. 1990. https://tromp.github.io/c4.html.

[2] James D. Allen. *The Complete Book of Connect 4: History, Strategy, Puzzles*. Puzzlewright Press, 2010.

[3] Louis Victor Allis. *A Knowledge-Based Approach of Connect-Four*. Report IR-163. Vrije Universiteit Amsterdam, The Netherlands, 1988.

[4] Pranav Avadhanam and Siddhartha G. Jena. Restricted positional games. 2021. Preprint, https://doi.org/10.48550/arXiv.2108.12839.

[5] József Beck. *Combinatorial Games: Tic-Tac-Toe Theory*. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2008.

[6] Jesper Makholm Byskov. Maker-Maker and Maker-Breaker games are PSPACE-complete. *BRICS Report Series*, 11(14), 2004.

[7] Noam D. Elkies. On numbers and endgames: combinatorial game theory in chess endgames. In *Games of No Chance, Proceedings of 7/94 MSRI Conference on Combinatorial Games*, pages 135–150. Cambridge University Press, 1996.

[8] Paul Erdős and John L. Selfridge. On a combinatorial game. *Journal of Combinatorial Theory*, 14:298–301, 1973.

[9] Florian Galliot, Sylvain Gravier, and Isabelle Sivignon. Maker-Breaker is solved in polynomial time on hypergraphs of rank 3. Preprint, https://arxiv.org/abs/2209.12819, 2022.

[10] Alfred W. Hales and Robert I. Jewett. Regularity and positional games. *Trans. Am. Math. Soc*, 106:222–229, 1963.

[11] Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó. *Positional Games*, volume 44 of *Oberwolfach Seminars*. Birkhäuser (Springer), 2014.

[12] Richard M. Karp. Reducibility among combinatorial problems. In R.E. Miller, J.W. Thatcher, and J.D. Bohlinger, editors, *Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, March 20–22, 1972*, chapter 9, pages 85–103. Springer US, Boston, MA, 2004.

[13] Md Lutfar Rahman and Thomas Watson. 6-uniform Maker-Breaker game is PSPACE-complete. In *Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)*, volume 187 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 57:1–15, 2021.

[14] Thomas J. Schaefer. On the complexity of some two-person perfect-information games. *Journal of Computer and System Sciences*, 16:185–225, 1978.

[15] Larry J Stockmeyer and Albert R Meyer. Word problems requiring exponential time (preliminary report). In *Proceedings of the Fifth Annual ACM Symposium on Theory of Computing*, pages 1–9, 1973.

[16] John Tromp. John's Connect Four Playground. http://tromp.github.io/c4/c4.html.

[17] John Tromp. Solving Connect-4 on medium board sizes. *ICGA Journal*, 31(2):110–112, 2008.
# A Appendix

## A.1 Proofs of Section 2

*Proof of Lemma 2.* At this point in the game, neither player wants to claim $y$, since it would free up $x$ and the opponent would win on the spot. Therefore, the game is just a parity game, with both players claiming all the vertices they can without claiming $y$. There are exactly $p(y)$ such vertices that can be claimed, including all the vertices that have already been claimed. If $p(y)$ is odd (resp. even), then Maker (resp. Breaker) will claim the last vertex that can be claimed without claiming $y$, after which Breaker (resp. Maker) will be forced to claim $y$ and Maker (resp. Breaker) will claim $x$ to win. □

*Proof of Theorem 3.* Let $\mathcal{G} = (X, \{\{x\}\}, P)$ be a poset positional game with $x \in X$ and $P$ has height 2. If $x$ is a minimal element, then Maker trivially wins. Thus we can assume that $x$ has at least one predecessor. One can partition the predecessors of $x$ into two sets $M$ and $B$ where $M$ (resp. $B$) contains the predecessors of $x$ such that $p(y)$ is even (resp. odd).

We claim that Maker wins if and only if $|M| \le |B|$. Firstly, suppose that $|M| \le |B|$. Then Maker repeatedly claims an unclaimed vertex in $M$ until all vertices in $M$ are claimed. At this point, $B$ contains at least one unclaimed vertex. Therefore, the last predecessor of $x$ to be claimed will be in $B$. By Lemma 2, this means that Maker wins. Finally, suppose that $|M| > |B|$. Then, similarly, Breaker wins by claiming vertices in $B$ – they will be all claimed before the vertices in $M$ are, and the last predecessor of $x$ to be claimed will be in $M$. By Lemma 2 again, Breaker wins. □

*Proof of Theorem 4.* Let $P$ be a poset of height 2 on a set $X$. We say the minimal elements of $P$ are the “bottom” vertices, and the others are the “top” vertices. For every relation $x < y$, we know $x$ is a bottom vertex and $y$ is a top vertex. Note that every vertex that is not comparable with any other vertex is a bottom vertex. We say that $x$ is a *private predecessor* of $y$ if $y$ is the only successor of $x$.

The poset positional game we consider is $\mathcal{G} = (X, \{\{y\}, y \text{ top vertex}\}, P)$. We will prove that Maker wins if and only if at least one of the following conditions holds:

1. $|X|$ is odd.

2. There exists a top vertex $y$ which does not have more private predecessors than non-private ones.

First note that these two conditions can be tested in polynomial time.

We prove that Maker wins under any of these two conditions. If condition 1 holds then, since Maker starts, she also plays last. Let $y$ be any top vertex. Maker plays as follows. She never claims $y$ or its last predecessor. When the last predecessor of $y$ is claimed, either it is claimed by Breaker and Maker wins by claiming $y$, or Maker has to claim it. In this case, as the total number of vertices is odd, there are at least two remaining vertices, all of which are top vertices. Therefore, Maker will win with her next move.

Assume now that Condition 2 holds, and let $y$ be a top vertex which does not have more private predecessors than non-private ones. Maker starts by claiming private predecessors of $y$ until all of them are claimed. Right after the last private predecessor of $y$ is claimed, since there are at least as many non-private predecessors of $y$ by assumption, there will be still some unclaimed predecessors of $y$ that are not private.

Then, as long as Breaker does not claim the last predecessor of $y$, Maker claims an arbitrary bottom vertex which is not the last predecessor of $y$, if possible. When the last predecessor $x$ of $y$ is claimed,
either it is claimed by Breaker and Maker wins by claiming $y$, or Maker has to claim it. The fact that Maker has to claim $x$ means that all the other bottom vertices have been claimed, so all the successors of $x$ are now available. Moreover, since $x$ is not a private predecessor of $y$, it has at least two successors. Therefore, even if Breaker claims one of them, Maker will claim another and win.

We now prove that Breaker wins when none of the conditions hold, i.e. when $|X|$ is even, and the property (*) “all the top vertices have strictly more private predecessors than non-private ones” holds. Note that the status of being private/non-private cannot change during the game.

We give a strategy for Breaker that maintains the property (*) throughout. Whenever Maker claims a bottom vertex $x$, Breaker answers as follows:

* If $x$ was the last predecessor of some top vertex $y$, then Breaker claims $y$. Since (*) was true before Maker's turn and $y$ has only one predecessor $x$, we know $x$ must be a private predecessor of $y$. In particular, there is no other top vertex that has been made available when Maker has claimed $x$. Moreover, (*) is still true after Breaker's move since the predecessors of the other top vertices have not changed.

* Otherwise, if $x$ was a private predecessor of some top vertex $y$ that has at least one non-private predecessor $x'$, then Breaker claims $x'$. Note that this way, (*) still holds for $y$ as well as for all the other top vertices.

* Otherwise, if there is a bottom vertex that is not a private predecessor of any top vertex, then Breaker claims an arbitrary such vertex. The property (*) still holds after this move.

* Otherwise, every bottom vertex is a private predecessor of some top vertex. Since the total number of vertices is even and it is Breaker's turn, there must be a top vertex $y$ with at least two (private) predecessors. Then Breaker claims an arbitrary predecessor of $y$. The property (*) still holds after this move.

By following this strategy, Breaker thus ensures that the property (*) is satisfied after each of his moves, so Maker will never be able to claim a top vertex. Therefore, Breaker wins. □

*Proof of Theorem 5.* The proof is a reduction from 3-SAT. Let $\phi$ be a 3-SAT formula. We build a poset positional game $\mathcal{G} = (X, \mathcal{F}, P)$ with $P$ of height 2 and winning sets of size 3 as follows:

* For any variable $x_i$ of $\phi$, we add four vertices $u_i, v_i, \overline{v_i}$ and $\tilde{v}_i$ in $X$.

* For any clause $C_j = l_{j1} \lor l_{j2} \lor l_{j3}$ in $\phi$, we add the winning set $S_j$ with, for $1 \le k \le 3$, $v_{jk} \in S_j$ if $l_{jk} = x_{jk}$, and $\overline{v_{jk}} \in S_j$ if $l_{jk} = \neg x_{jk}$.

* For any variable $x_i$ of $\phi$, we add the relations $u_i < v_i$, $u_i < \overline{v_i}$ and $u_i < \tilde{v}_i$ in $P$.

We prove that $\phi$ is satisfiable if and only if Breaker wins the poset positional game played on $\mathcal{G}$. Suppose first that $\phi$ is satisfiable and let $\nu$ be a valuation that satisfies $\phi$. We consider the following strategy for Breaker:

* Whenever Maker claims a vertex $u_i$, if $x_i$ is set to True in $\nu$ then Breaker claims $v_i$, and if $x_i$ is set to False in $\nu$ then Breaker claims $\overline{v_i}$.

* Whenever Maker claims a vertex in $\{v_i, \overline{v_i}, \tilde{v}_i\}$, Breaker claims the remaining vertex in $\{v_i, \overline{v_i}, \tilde{v}_i\}$.

Note that, since Maker starts, these moves are always possible. For each winning set $S_j$, by assumption, $\nu$ satisfies the corresponding clause $C_j$ by assumption. Thus, there exists some $l_{jk} \in C_j$ that is evaluated to True. If this literal is $x_{jk}$, then Breaker has claimed $v_{jk} \in S_j$, and if it is $\neg x_{jk}$ then Breaker has claimed $\overline{v_{jk}} \in S_j$. Thus, Breaker wins.

Conversely, suppose that $\phi$ is not satisfiable, and consider the following strategy for Maker:
* As her first move, Maker claims some arbitrary $u_j$.

* Whenever Breaker claims a vertex of some pair $\{v_i, \overline{v_i}\}$, Maker responds by claiming the other, if it is still available. Otherwise, Maker claims an arbitrary vertex.

When all the vertices have been claimed, Maker has claimed at least one vertex in each pair $\{v_i, \overline{v_i}\}$. Consider the valuation $\nu$ such that, for all $i$, $x_i$ is True if and only if Breaker has claimed $v_i$. As Breaker could not have claimed both $v_i$ and $\overline{v_i}$ for any $i$, we know that Maker has claimed all the vertices corresponding to literals that are false under $\nu$. On the other hand, since $\phi$ is not satisfiable by assumption, there exists some clause $C_j$ whose literals are all false under $\nu$. This means all three vertices of $S_j$ have been claimed by Maker, so Maker has won the game. $\square$

*Proof of Theorem 6.* We reduce from the problem SET COVER. A set cover of a hypergraph $H = (V, E)$ is a set $S \subseteq E$ of edges such that every vertex of $H$ belongs to some edge in $S$. Given an integer $k$, deciding if a given hypergraph contains a set cover of cardinality $k$ is NP-complete [12].

Let $H = (V, E)$ be a hypergraph, and let $k$ be an integer. We assume that any vertex of $H$ is in at least one edge. We construct a poset positional game $\mathcal{G}_H = (X, \mathcal{F}, P)$ as follows. Define $m := |E|$ and $n := |V|$. The set of vertices $X$ is the union of:

* $X_V$, a set of size $n$, in one-to-one correspondence with $V$;

* $X_E$, a set of size $m$, in one-to-one correspondence with $E$;

* $X_M$, a set of size $m-k$;

* $X_B$, a set of size $n-k$;

* $x$ and $y$, two additional vertices.

There are $2(n+m-k+1)$ vertices in total. The set $\mathcal{F}$ contains a unique winning set $\{x\}$. As for the definition of $P$, we have $v < u$ in the following cases:

* $v \in X_M$ and $u \in X_V$;

* $v \in X_E$, $u \in X_V$, and $u \in v$ in $H$;

* $v \in X_E$, $u \in X_B$;

* $v \in X_V \cup X_B$, $u = x$;

* $v \in X_B$, $u = y$.

See Figure 3 for an illustration of the structure of the game. Note that $P$ has height 3. The predecessors of $x$ are in $X_V$ and $X_B$. Moreover, for all $v \in X_V$, $p(v) = 2(n+m-k)$ is even, and for all $u \in X_B$, $p(u) = 2(n+m-k)-1$ is odd. We will say a subset of $X$ is empty if all its vertices have been claimed: with Lemma 2 in mind, Maker wants $X_V$ to be empty before $X_B$ is.

We will prove that $H$ has a set cover of size $k$ if and only if Breaker wins the game $\mathcal{G}_H$.

First of all, suppose that $H$ has a set cover of size $k$, $S = \{e_1, e_2, ..., e_k\}$. Both players can only claim vertices in $X_M \cup X_E$ until either $X_M$ or $X_E$ is empty. During the first $m-k$ rounds, Breaker's strategy is the following. Whenever Maker claims a vertex in $X_E \setminus S$, Breaker claims an arbitrary vertex in $X_M$. Otherwise, Breaker claims an arbitrary vertex in $X_E \setminus S$. This ensures that $X_E \setminus S$ is empty after exactly $m-k$ rounds. Note that, among the first $m-k+1$ moves of Maker, she has necessarily claimed at least one vertex in $S$. Indeed, there are $2(m-k)$ vertices in $X_M \cup (X_E \setminus S)$, moreover any vertex in $X_V \cup X_B$ has a predecessor in $S$ and thus cannot be claimed while all vertices in $S$ are unclaimed. Therefore, after the $(m-k+1)^{th}$ move of Maker, $2(m-k)+1$ vertices have been claimed, all of which are in $X_M \cup X_E$, including all the vertices in $X_E \setminus S$ and at least one
<figure><img src="image_6.png" /><figcaption>Figure 3: Reduction from SET COVER to MB POSET POSITIONAL GAME. A solid arc means that all the possible relations are in the poset. The winning set is represented by a red circle.</figcaption></figure>

vertex in $S$. This means that at most $k-1$ vertices in $X_E$ are unclaimed at this point. Breaker goes on to claim vertices in $X_E$ until it is empty (at most $k-1$ additional moves), and then moves on to claiming vertices in $X_B$ until is is empty (at most $n-k$ additional moves). During this time, Maker cannot claim all $n$ vertices in $X_V$, so the last predecessor of $x$ to be claimed will be in $X_V$. By Lemma 2, Breaker wins.

Now, suppose that $H$ has no set cover of size $k$. This means in particular that for any set $S \subseteq E$ of $i \le k$ edges, at least $k-i+1$ vertices of $V$ are not covered by any edge in $S$. Indeed, one could otherwise add $k-i$ edges to cover all the vertices and obtain a set cover of size $k$. We provide a strategy for Maker, in three stages. She starts by claiming an arbitrary vertex in $X_M$. She then answers the first $m-k-1$ moves of Breaker as follows:

(a1) if Breaker claims a vertex in $X_E$, then Maker claims an arbitrary vertex in $X_M$;

(a2) otherwise, Breaker can only claim a vertex in $X_M$, and then Maker claims an arbitrary vertex in $X_E$.

This concludes the first stage. At this point, $X_M$ is empty, and exactly $m-k-1$ vertices have been claimed in $X_E$. In the second stage, Maker answers the next $k+1$ moves of Breaker as follows:

(b1) if Breaker claims a vertex in $X_E$, then Maker claims an arbitrary vertex in $X_V$;

(b2) otherwise, Breaker can only claim a vertex in $X_V$, and then Maker claims an arbitrary vertex in $X_E$.

First of all, note that Maker is always able to play the move in (b1). Indeed, consider that $i$ moves, $1 \le i \le k$, have been played by Breaker in the second stage (including his last move in $X_E$). Then $k+1-i$ vertices remain unclaimed in $X_E$, and $n-i$ vertices are unclaimed in $X_V$. The $k+1-i$ unclaimed vertices in $X_E$ correspond to a set of edges of cardinality $k+1-i \le k$. As we observed earlier, at least $i$ vertices of $V$ are not covered by this set and thus have all their predecessors claimed already. Of those vertices, at most $i-1$ have already been claimed, so at least one vertex in $X_V$ can be claimed by Maker.

After the second stage, $X_E$ is empty, $n-k-1$ vertices remain unclaimed in $X_V$, and $n-k$ vertices remain unclaimed in $X_B$. Therefore, Maker can claim all the remaining vertices in $X_V$ before Breaker claims all the vertices in $X_B$. By Lemma 2, Maker wins. $\square$
## A.2 Proofs of Section 3

*Proof of Theorem 7.* The reduction is done from 3-QBF, which has been proved PSPACE-complete by Stockmeyer and Meyer [15].

### 3-QBF

**Input:** A formula of the form $\psi = \forall x_1 \exists x_2 \dots \forall x_{2n-1} \exists x_{2n} \phi(x_1, \dots, x_{2n})$ where $\phi$ is a 3-CNF formula.

**Output:** The truth value of $\psi$.

The result is obtained by reduction from 3-QBF. Let $\psi = \forall x_1 \exists x_2 \dots \forall x_{2n-1} \exists x_{2n} \phi$ be a 3-QBF formula.

A classical equivalent formulation of 3-QBF is to consider that two players, Satisfier and Falsifier, are choosing the valuations of the variables, with Falsifier starting and choosing the valuations of the odd variables whereas Satisfier chooses the valuations of the even variables. Satisfier wins if the valuation created by their moves satisfies $\phi$, otherwise Falsifier wins.

We build a poset positional game $\mathcal{G} = (X, \mathcal{F}, P)$ as follows:

* For any $1 \le i \le 2n$, we add two vertices $v_i$ and $\overline{v_i}$ in $X$.

* For any $1 \le i \le 2n - 1$, we also add a vertex $u_i$.

* For any clause $C_j = l_{i_1} \lor l_{i_2} \lor l_{i_3}$ in $\phi$, we add a winning set $S_j \in \mathcal{F}$. For $1 \le k \le 3$, we have $v_{i_k} \in S_j$ if $l_{i_k} = x_{i_k}$ and $\overline{v_{i_k}} \in S_j$ if $l_{i_k} = \neg x_{i_k}$.

* For any $1 \le i \le 2n - 1$, we add in $P$ the relations $v_i < u_i$, $\overline{v_i} < u_i$, $u_i < v_{i+1}$ and $u_i < \overline{v_{i+1}}$.

See Figure 1 for an example of the reduction. We now prove that Falsifier wins on $\psi$ if and only if Maker wins in $\mathcal{G}$. First note that, because of the poset $P$, the moves are almost all forced. For any $1 \le i \le n$, Maker chooses one of $v_{2i-1}$ or $\overline{v_{2i-1}}$, then Breaker has to claim the other and Maker has to claim $u_{2i-1}$. Breaker then chooses one of $v_{2i}$ or $\overline{v_{2i}}$, Maker has to claim the other and Breaker has to claim $u_{2i}$, and so on.

Now suppose that Falsifier has a winning strategy $S$ on $\psi$. We define Maker's strategy as follows. For any $1 \le i \le n$, when Maker has to choose between $v_{2i-1}$ and $\overline{v_{2i-1}}$, she considers that all the variables $x_k$ with $k < 2i - 1$ such that Maker has claimed $v_k$ are set to False, and the others to True. If, according to $S$, Falsifier has to put $x_{2i-1}$ to True, then Maker claims $\overline{v_{2i-1}}$, otherwise she claims $v_{2i-1}$. Since $S$ is a winning strategy for Falsifier, at the end of the game there exists a clause $C_j$ that is not satisfied by the valuation provided by Satisfier and Falsifier, i.e. all its literals are false. By construction, the three corresponding vertices will be claimed by Maker, who will have claimed all the vertices of the winning set $S_j$.

Conversely, suppose Satisfier has a winning strategy $S$ on $\psi$. We define Breaker's strategy as follows. For any $1 \le i \le n$, when Breaker has to choose between $v_{2i}$ and $\overline{v_{2i}}$, he considers that all the variables $x_k$ with $k < 2i$ such that Maker has claimed $v_k$ are set to False, and the others to True. If, according to $S$, Satisfier has to put $x_{2i}$ to True, then Breaker claims $\overline{v_{2i}}$, otherwise he claims $v_{2i}$. Since $S$ is a winning strategy for Satisfier, at the end of the game every clause $C_j$ contains a literal that is true. By construction, the corresponding variable will be claimed by Breaker, who will have claimed at least one vertex in each $S_j$. $\square$

*Proof of Theorem 8.* We proceed by dynamic programming. Let $\mathcal{G} = (X, \mathcal{F}, P)$ be a poset positional game. Let $\mathcal{F} = \{S_1, \dots, S_m\}$ be the winning sets of $\mathcal{G}$. We characterize the games that can be
reached from a game played on $\mathcal{G}$ using an antichain $Y$ of $X$ and a boolean vector $B = (b_1, ..., b_m) \in \{0, 1\}^m$. We define the game $\mathcal{G}(Y, B)$ as follows:

* The set of vertices of $\mathcal{G}(Y, B)$ is $X(Y, B) = \{x \in X \mid \exists y \in Y, y \le x\}$.

* The set of winning sets of $\mathcal{G}(Y, B)$ is $\mathcal{F}(Y, B) = \{S_i \cap X(Y, B) \mid 1 \le i \le m \text{ and } b_i = 1\}$.

* The poset of $\mathcal{G}(Y, B)$ is $P$ restricted to $X(Y, B)$.

* As usual, Maker is the next player.

The set $Y$ corresponds to the available moves. The vector $B$ registers, for each winning set $S_i$, whether it contains an element that has already been claimed by Breaker (then $b_i = 0$) or not (then $b_i = 1$). In the latter case, it means that Maker has claimed all the elements of $S_i$ below $Y$, so she will win if she claims the other elements of $S_i$. Note that the initial game $\mathcal{G}$ corresponds to $\mathcal{G}(Y_{\min}, (1, ..., 1))$ where $Y_{\min}$ is the set of minimal elements of $P$. The outcome of $\mathcal{G}(Y, B)$ can be computed inductively as follows:

1. If $Y$ contains a winning set $S'_i \in \mathcal{F}(Y, B)$ of size 1, then Maker wins.

2. If all $b_i$'s are 0, then Breaker wins.

3. Assume Conditions 1 and 2 are not met, and consider the next round. Let $u \in Y$ be a possible move for Maker. Note that Maker cannot win instantly with this move since condition 1 is not met. Let $Y^u$ be the set of minimal elements after $u$ is claimed, and let $v \in Y^u$ be a possible answer of Breaker. Finally, let $Y^{uv}$ be the set of minimal elements after $v$ is claimed. We define $B^{uv} \in \{0, 1\}^m$ as follows: for each $1 \le i \le m$, let $b_i^{uv} = 0$ if $v \in S_i$, otherwise let $b_i^{uv} = b_i$. Then Maker wins $\mathcal{G}(Y, B)$ if and only if there exists $u \in Y$ such that, for all $v \in Y^u$, Maker wins $\mathcal{G}(Y^{uv}, B^{uv})$.

The algorithm consists in computing the outcome of all subgames, starting with $Y = \emptyset$, and traversing the subgames in increasing order of $|X(Y, B)|$. Let us analyze the complexity of the algorithm. There are at most $|X|^w$ antichains in a poset of width $w$ on $|X|$ elements, and at most $2^m$ possible values for $B$. Thus there at most $|X|^{w2^m}$ games $\mathcal{G}(Y, B)$ to consider. Computing the outcome of $\mathcal{G}(Y, B)$, when already knowing the outcome of $\mathcal{G}(Y', B')$ for every antichain $Y'$ above $Y$, can be done in time $O(w^4)$. Indeed, there are $O(w^2)$ choices for the moves $u$ and $v$ of Maker and Breaker, and computing $Y^{uv}$ from $Y$ can be done in time $O(w^2)$. Consequently, the time complexity of the algorithm is $O(|X|^{w2^mw^4})$. $\square$

## A.3 Proofs of Section 4

*Proof of Theorem 11.* The “if” direction is a direct consequence of Lemmas 9 and 10. Let us prove the “only if” direction: we suppose that none of the three conditions hold, and we show that Breaker wins. In particular, all winning sets are black (we may assume that there exists at least one) and no minimal element is a winning set. Additionally, we are in one of two cases:

* Case 1: $|X|$ is even. This means there is an even number of chains of odd size, i.e. $|Y|$ is even where $Y$ denotes the set of all black minimal elements. Breaker's strategy is the following. Whenever Maker claims a vertex in $Y$, Breaker also claims an arbitrary vertex in $Y$. Otherwise, Maker necessarily claims a white vertex, so Breaker claims its successor (which always exists since all maximal elements are black). Using this strategy, Breaker ensures to claim every black vertex in $X \setminus Y$, so he wins.

* Case 2: $|X|$ is odd and all the winning sets are part of the same chain $C_i$. Let $j$ be maximum such that $\{x_{i,j}\} \in \mathcal{F}$, and let $Y$ be the set of all vertices which are not greater or equal to $x_{i,j+1}$. Since $|X|$ is odd and $x_{i,j+1}$ is white, we know $|Y|$ is even. Breaker's strategy is the
following. Whenever Maker claims a vertex in $Y$, Breaker also claims an arbitrary vertex in $Y$. Otherwise, Maker necessarily claims a white vertex in $C_i$, so Breaker claims its successor (unless Maker has claimed $x_{i,1}$ specifically, in which case Breaker plays an arbitrary move). Using this strategy, Breaker ensures to claim every black vertex in $X \setminus Y$, so he wins. $\square$

To prove Lemma 13, we need two technical lemmas.

**Lemma 16.** If $|X|$ is even and Maker has a winning strategy in $G'$, then she has a winning strategy in $G'$ such that she never claims $x_{i,j+1}$ unless it makes her win on the spot.

*Proof.* Let $S$ be a winning strategy for Maker in $G'$. If, at any point during the game, Maker claims $x_{i,j+1}$ without winning instantly, then Breaker is forced to claim $x_{i,j}$, otherwise Maker would win on her next turn. Let $S'$ be the same strategy as $S$ with the exception that, when Maker should claim $x_{i,j+1}$, she skips this claim (and the forced answer $x_{i,j}$ of Breaker) and goes on with the game, following the strategy $S$ as if that round had happened. Breaker will never claim $x_{i,j+1}$, otherwise he would lose immediately. Note that, since $x_{i,j+1}$ is white, there will always be another vertex for Breaker to claim. At some point in $S$, Maker will fill up a winning set $W \in \mathcal{F}'$. If $x_{i,j+1} \notin W$, then $W$ will also be filled up in $S'$. If $x_{i,j+1} \in W$, then at some point in $S'$ Maker will have claimed all the vertices of $W$ except for $x_{i,j+1}$: in this case, Maker wins on the spot by claiming $x_{i,j+1}$, satisfying the statement of the lemma. $\square$

We give a similar result for Breaker.

**Lemma 17.** If $|X|$ is odd and Breaker has a winning strategy in $G'$, then he has a winning strategy in $G'$ where he never claims $x_{i,j-1}$.

*Proof.* Consider a winning strategy $S$ for Breaker in $G'$. Note that Breaker never claims $x_{i,j+1}$ in $S$, otherwise he would lose immediately. We now define a new strategy $S'$ as follows. Breaker plays according to $S$ until, inevitably, Maker claims $x_{i,j+1}$: at this point, Breaker claims $x_{i,j}$, but he then goes on with $S$ as if that last round had not happened. In particular, Breaker will never be told to claim $x_{i,j-1}$, as this vertex is not even available in this narrative. Therefore, Maker will eventually claim $x_{i,j-1}$: only at this moment does Breaker input into $S$ Maker's claims of $x_{i,j+1}$ (prompting the answer $x_{i,j}$ of Breaker) and $x_{i,j-1}$ successively. Breaker then follows $S$ until the end, winning the game without claiming $x_{i,j-1}$. $\square$

*Proof of Lemma 13.* Firstly, suppose Maker has a winning strategy $S'$ in $G'$. If $|X|$ is even, then we further assume that $S'$ satisfies the property from Lemma 16. Up to playing arbitrary moves after filling up a winning set, assume that $S'$ continues until all vertices in $X'$ are claimed. The idea is the following: Maker will fill up a winning set of $G'$, and also claim all the white vertices in $Y$. By definition of $G'$, this will automatically ensure that Maker fills up a winning set of $G$. We now explain how she achieves this:

* Case 1: $|X|$ is odd. Maker plays her first move $x \in X'$ according to $S'$. Since $|X' \setminus \{x\}|$ and $|Y|$ are both even, Maker can then use the following strategy. Whenever Breaker plays inside $X'$, Maker answers inside $X'$ according to $S'$, thus ensuring to eventually fill a winning set of $G'$. Otherwise i.e. whenever Breaker claims some (black) $y \in Y$, Maker claims the (white) successor of $y$, thus ensuring to claim all the white vertices in $Y$.

* Case 2: $|X|$ is even. Maker plays according to $S'$ until $x_{i,j+1}$ is claimed. Assume it is claimed by Maker, otherwise she wins immediately by claiming $x_{i,j}$. By the property from Lemma 16, Maker has already filled up a winning set of $G'$ at this point, so she just needs to claim all the white vertices of $Y$. Breaker is forced to claim $x_{i,j}$, and then Maker claims $x_{i,j-1}$. From this
point on, since $j-2$ is odd, Maker can force Breaker to claim all the black vertices in $Y$, and
claim all their (white) successors herself.

Lastly, suppose Breaker has a winning strategy $S'$ in $G'$. If $|X|$ is odd, then we further assume that $S'$ satisfies the property from Lemma 17. The idea is the following: Breaker will claim a vertex in each winning set of $G'$, and also claim all the black vertices in $Y$. By definition of $G'$, this will automatically ensure that Breaker claims a vertex in each winning set of $G$. We now explain how he achieves this:

* Case 1: $|X|$ is even. Since $|X'|$ and $|Y|$ are both even, Breaker can then use the following strategy. Whenever Maker plays inside $X'$, Breaker answers inside $X'$ according to $S'$, thus ensuring to claim a vertex in each winning set of $G'$. Otherwise i.e. whenever Maker claims some (white) $y \in Y$, Breaker claims the (black) successor of $y$, thus ensuring to claim all the black vertices in $Y$.

* Case 2: $|X|$ is odd. Breaker plays according to $S'$ until Maker claims $x_{i,j-1}$, which will necessarily happen by the property from Lemma 17. Breaker pretends like that move did not happen i.e. does not input that claim into $S'$, and claims $x_{i,j-2}$ himself. At this point, the number of unclaimed vertices in $X'$ is even, so that, whenever Maker plays inside $X'$, Breaker can answer inside $X'$ according to $S'$. This will force Maker to claim all the white vertices in $Y \setminus \{x_{i,1}\}$, with Breaker claiming the (black) successor each time. Eventually, Maker will have to claim $x_{i,1}$, at which point Breaker inputs Maker's earlier claim of $x_{i,j-1}$ into $S'$. The sets of vertices claimed by both players in $S'$ now coincide with reality, which ensures that Breaker claims a vertex in each winning set of $G'$.

*Proof of Theorem 14.* Our algorithm is based on a dynamic programming approach. As before, we consider a poset positional game $\mathcal{G} = (X, \mathcal{F}, P)$ where $P$ is made of pairwise disjoint chains. We use the same notations and coloring than before. Thanks to Lemmas 9 and 13, we can reduce the number of sub-positions to consider. Indeed, we can assume that each chain contains at most one (black) winning set of size 1. Our algorithm computes dynamically the outcome of all these "useful" positions. A sub-position will be given by two $w$-uplets : $K = (k_1, ..., k_w)$ with $0 \le k_i \le l_i$ corresponding to the heights of the chains in the sub-position, and $W = (s_1, ..., s_w)$ with $0 \le s_i \le k_i$ corresponding to the index of a black winning set of size 1 on the $i$-th chain that might be created during the game. We will only consider values of $s_i$ that either are zero (no winning set of size 1 on the $i$-th chain) or do not have the same parity as $|X|$ (so that $x_{i,s_i}$ is necessarily black) and such that there is a winning set $\{x_{i,s_i}, u\}$ in $\mathcal{F}$. The game $\mathcal{G}(K, W)$ is formally defined as follows:

* The vertices $X(K, W)$ of $\mathcal{G}(K, W)$ on the $i$-th chain are:

- if $s_i = 0$: the vertices $x_{i,1}$ to $x_{i,k_i}$,

- if $s_i > 0$ and $|X|$ is even: the vertices $x_{i,1}$ to $x_{i,s_i-1}$,

- if $s_i > 0$ and $|X|$ is odd: the vertices $x_{i,1}$ to $x_{i,s_i-2}$.

* The poset $P(K, W)$ is the poset induced by $P$ on $X(K, W)$.

* The set $\mathcal{F}(K, W)$ contains all sets $\{x_{i,s_i}\}$ where $s_i \neq 0$, and additionally, for each $S \in \mathcal{F}$:

- If $S$ has an element $x_{i,j}$ with $j > k_i$, then $S$ is ignored.

- If $S$ has a black element $x_{i,j}$ with $j < s_i$, then $S$ is ignored.

- Otherwise, if $|X|$ is even (resp. odd), we add $S \setminus \{x_{i,j}, j < s_i\}$ (resp. $S \setminus \{x_{i,j}, j < s_i - 1\}$) to the set of winning sets $\mathcal{F}(K, W)$. By doing this, we might add an empty winning set to $\mathcal{F}(K, W)$, which actually means that Maker wins trivially.
• As usual, Maker is the next player.

Note that initial game $\mathcal{G}$ corresponds to the game $\mathcal{G}(K, W)$ with $K = (\ell_1, \dots, \ell_w)$ and $W = (0, \dots, 0)$. We compute the outcome from increasing total number of vertices.

Let $\mathcal{G}(K, W)$ be a position. We first list some trivial cases, using Lemmas 9 and 10:

• If there are no winning sets, then Breaker wins.

• If there is an empty winning set, then Maker wins.

• If there is a winning set of size 1 which is white or minimal, then Maker wins.

• If there is a winning set made of two white vertices on the same chain, then Maker wins.

• If there are two black winning sets of size 1 on different chains and $|X|$ is odd, then Maker wins.

In particular, that last item applies as soon as there are two positive $s_i$'s and $|X|$ is odd. The fourth item comes from the fact that Maker can apply Lemma 9 twice in a row to claim both vertices of the winning set.

Assuming none of these trivial cases hold, we consider every possible move $x_{i,j}$ of Maker and every possible answer $x_{i',j'}$ of Breaker in the first round. Each choice leads to a sub-position $\mathcal{G}(K', W')$. We define $K' = (k'_1, \dots, k'_w)$ as follows: $k'_i = k_i - 1$, $k'_{i'} = k_{i'} - 1$ (or, if $i = i'$: $k'_i = k_i - 2$), and all the others values in $K'$ are equal to the corresponding values in $K$. As for $W' = (s'_1, \dots, s'_w)$, its definition depends on $x_{i,j}$ and $x_{i',j'}$.

• Suppose $x_{i,j}$ is in no winning set. Then $W' = W$ except that we define $s'_{i'} = 0$ if $j' = s_{i'}$.

• Suppose $x_{i,j}$ is in at least one winning set. Let $U$ be the set of all vertices $u$ such that $\{x_{i,j}, u\} \in \mathcal{F}(K, W)$ and $u$ is not claimed by Breaker (i.e. $u \neq x_{i',j'}$). Then, for each $u \in U$, $\{u\}$ is a winning set after the first round. We assume that $S$ only contains black vertices, otherwise Maker wins. For each $i''$, let $s''_{i''}$ be the maximum between $s_{i''}$ and all the $j''$ such that $x_{i'',j''} \in U$. Lemma 13 ensures that, with this definition of $W'$, the game $\mathcal{G}(K', W')$ is indeed equivalent to this case.

Knowing all the possible outcomes after these two moves, one can compute the outcome of $\mathcal{G}(K, W)$. If there exists a move of Maker such that, for any Breaker answer, the resulting game $\mathcal{G}(K', W')$ is winning for Maker, then Maker wins. Otherwise, Breaker wins.

There are $(h+1)^w$ possible values for $K$ and also $([h/2] + 1)^w$ possible values for $W$ (since the winning sets of size 1 must be black) hence $O(h^{2w}/2^w)$ positions to consider. To compute the outcome of a position, one needs to consider $O(w^2)$ potential pairs of moves. Each given pair may require to go through the whole set of winning sets, which is of size $|\mathcal{F}| = O((hw)^2)$. All in all, the running time of the algorithm is $O(h^{2w}/2^w * w^2 * h^2 w^2) = O(h^{2(w+1)})$. $\square$

*Proof of Theorem 15.* Let $x_1, \dots, x_t, y_1, \dots, y_t$ be the vertices of the chains of height 2, with $x_i < y_i$ for all $1 \le i \le t$. Let $x_{t+1}, \dots, x_w$ be the other vertices if there are any. We say the $x_i$ are the "bottom" vertices and the $y_j$ are the "top" vertices. We consider two cases depending on the parity of $|X|$.

• Firstly, suppose $|X|$ is odd, which means Maker plays the first and the last move. There are several easy winning situations for Maker (note that the first three actually hold regardless of parity), all of which can clearly be identified in time $O(|X|^2)$ since there are $O(|X|^2)$ winning sets:
1. There is a winning set of the form $\{x_i\}$. Indeed, Maker simply claims $x_i$ as her first move.

2. There are two winning sets of the form $\{x_i, x_j\}$ and $\{x_j, x_k\}$. Indeed, Maker starts by claiming $x_j$ and will claim either $x_i$ or $x_k$ as her second move to win.

3. There are two winning sets of the form $\{x_i, x_j\}$ and $\{x_i, y_i\}$. Indeed, Maker starts by claiming $x_i$ and will claim either $x_j$ or $y_i$ as her second move to win.

4. There is a winning set of the form $\{x_i, y_j\}$ with $i \neq j$. Indeed, Maker starts by claiming $x_i$, the parity then allows her to wait until Breaker claims $x_j$, at which point she claims $y_j$ and wins.

5. There is a winning set in which each vertex is a top vertex. Indeed, using the parity, Maker can ensure to claim all the top vertices in the game. For this, she starts by claiming $x_{t+1}$ (that exists since the total number of vertices is odd). Each time Breaker claims some $x_i$, Maker claims $y_i$ if $i \le t$ or some $x_j$ with $j > t$ if $i > t$.

We actually claim that those are the only winning situations for Maker. Indeed, suppose none of the above apply: then the winning sets are pairwise disjoint and all of them are of the form $\{x_i, x_j\}$ or $\{x_i, y_i\}$, so whenever Maker claims a vertex of a winning set it is possible for Breaker to immediately claim the other.

* Secondly, suppose $|X|$ is even, which means Breaker plays the last move. We then introduce the following reduction rules:

R1: Assume there exists a winning set of the form $\{x_i, x_j\}$ that is disjoint from all the other winning sets. Then remove $x_i$ and $x_j$.

R2: Assume there exists a nonempty set of indices $I \subseteq \{1, \dots, t\}$ such that all the winning sets that contain some $x_i$ with $i \in I$ also contain some $y_j$ with $j \in I$. Then remove all vertices with indices in $I$.

Claim 1: The reductions R1 and R2 are outcome-neutral when Maker is the first player.

Let us prove Claim 1 (note that the proof heavily relies on the parity assumption):

- Let $\mathcal{G}'$ be a reduced game obtained from $\mathcal{G}$ through R1. If Maker wins $\mathcal{G}'$, then she wins $\mathcal{G}$ by claiming $x_i$ as her first move: indeed, this forces Breaker to claim $x_j$, and we get the game $\mathcal{G}'$. If Breaker wins $\mathcal{G}'$, then he wins $\mathcal{G}$ by following his winning strategy on $\mathcal{G}'$ whenever Maker does not play inside $\{x_i, x_j\}$, and only claiming $x_i$ or $x_j$ when Maker claims the other. However, we need to be careful that Breaker might be forced to claim $x_i$ or $x_j$ before Maker does. Because of the parity assumption, this can only happen if, say, $i \le t$ and $j > t$, and $x_i, y_i, x_j$ are the only three vertices remaining. In this case, Breaker simply claims $x_j$: Maker must claim $x_i$ and Breaker claims $y_i$, ensuring the win since $x_i$ is in no other winning set.

- Let $\mathcal{G}'$ be a reduced game obtained from $\mathcal{G}$ through R2, and let $X_I$ be the set of vertices with indices in $I$. Then whoever wins $\mathcal{G}'$ also wins $\mathcal{G}$, by following their winning strategy on $\mathcal{G}'$ whenever their opponent does not play inside $X_I$, and claiming $y_i$ whenever their opponent claims $x_i$ for some $i \in I$. This strategy clearly works for Maker, who is going to fill up a winning set of the game $\mathcal{G}'$. As for Breaker, due to the parity assumption, this strategy ensures that he gets all top vertices of $X_I$, which takes care of all winning sets that are not in the game $\mathcal{G}'$ by definition of $I$.

This ends the proof of Claim 1.
We define a *good pattern* as a sequence of winning sets of the following form:

({$x_{i_1}$, $x_{i_2}$}, {$x_{i_2}$, $y_{i_3}$}, {$x_{i_3}$, $y_{i_4}$}, {$x_{i_4}$, $y_{i_5}$}, ..., {$x_{i_{\ell-1}}$, $y_{i_\ell}$}), with $\ell \ge 3$ and pairwise distinct $i_k$.

We define a *winning pattern* as a good pattern (with notations as above) prolonged with a winning set of the form {$x_{i_\ell}, z$} where either: $z \in \{x_{i_2}, \dots, x_{i_{\ell-1}}\}$, $z \in \{y_{i_1}, y_{i_2}\}$, or $z$ is a bottom vertex that does not appear in the good pattern. See Figure 4.

<figure><img src="image_7.png" /><figcaption>Figure 4: A winning pattern where $z$ is a bottom vertex that does not appear in the good pattern.</figcaption></figure>

**Claim 2:** If the game contains a winning pattern, then Maker wins.

Let us prove Claim 2. Maker starts by claiming $x_{i_2}$, which forces Breaker to claim $x_{i_1}$ because of the winning set {$x_{i_1}$, $x_{i_2}$}. Then Maker claims $x_{i_3}$, which forces Breaker to claim $y_{i_3}$ because of the winning set {$x_{i_2}$, $y_{i_3}$}. Then Maker successively claims $x_{i_4}, \dots, x_{i_\ell}$, which forces Breaker to successively claim $y_{i_4}, \dots, y_{i_\ell}$ in similar fashion. If $z \in \{x_{i_2}, \dots, x_{i_{\ell-1}}\}$, then Maker has already filled up the winning set {$x_{i_\ell}, z$} and thus won the game. Otherwise, either $z \in \{y_{i_1}, y_{i_2}\}$ or $z$ is a bottom vertex that does not appear in the good pattern: in both cases, $z$ is an available vertex, so Maker can now claim $z$ to win by filling up the winning set {$x_{i_\ell}, z$}. This ends the proof of Claim 2.

**Claim 3:** If there exists at least one winning set and neither R1 nor R2 applies, then Maker wins.

Let us prove Claim 3. Suppose there exists at least one winning set and neither R1 nor R2 applies. Let us first settle the case $t=0$ (all vertices are bottom): since R1 does not apply, there exists a winning set of the form {$x_i$} or two winning sets of the form {$x_i, x_j$} and {$x_j, x_k$}, so Maker wins in at most two rounds. Therefore, we now assume $r \ge 1$.

We start by showing the existence (in all nontrivial cases) of a good pattern. There exists a winning set $W$ in which each vertex is a bottom vertex, otherwise R2 would apply to the set $I = \{1, \dots, t\}$. Maker wins trivially if $|W| = 1$, so assume $W = \{x_p, x_q\}$ for some $p \ne q$. Since R1 does not apply, we know that at least one of $x_p$ or $x_q$, say $x_q$, is part of a winning set $W' \ne W$. If $W' = \{x_q\}$, $W' = \{x_q, y_p\}$, $W' = \{x_q, y_q\}$ or $W' = \{x_q, x_r\}$ for some $r \ne p, q$, then Maker wins the game in at most two rounds, so assume $W' = \{x_q, y_r\}$ for some $r \ne p, q$. Therefore, there exist good patterns: $(W, W')$ is one.

Now, we will show the existence (in all nontrivial cases) of a winning pattern. Let $I$ be the set of all indices of top vertices that appear in good patterns. Note that $I \ne \emptyset$ and $I \subseteq \{1, \dots, t\}$. Since R2 does not apply to the set $I$, we know there exists $j \in I$ such that there exists a winning set of the form {$x_j, z$} where $z \notin \{y_i, i \in I\}$ (assuming {$x_j$} is not a winning set, otherwise Maker trivially wins). Let ($\{x_{i_1}, x_{i_2}\}$, $\{x_{i_2}, y_{i_3}\}$, $\{x_{i_3}, y_{i_4}\}$, $\{x_{i_4}, y_{i_5}\}$, ..., $\{x_{i_{\ell-1}}, y_{i_\ell}\}$) be a good pattern where $i_\ell = j$, which exists since $j \in I$. Since $z \notin \{y_i, i \in I\}$, this good pattern does not contain $z$ as a top vertex, nor can it be prolonged into a longer good pattern by the winning set {$x_j, z$}. Moreover, we can also assume that $z \ne x_{i_1}$, otherwise Maker wins the game in two rounds by claiming $x_{i_1}$ as her first move. All in all, this leaves us with three possibilities:
$z \in \{x_{i_2}, \dots, x_{i_{l-1}}\}$, $z \in \{y_{i_1}, y_{i_2}\}$, or $z$ is a bottom vertex that does not appear in the good pattern. In all cases, we get a winning pattern by definition, so Claim 2 ensures that Maker wins. This ends the proof of Claim 3.

Finally, we should explain how to detect in $O(|X|^3)$ time whether R2 applies or not. It suffices, for each index $1 \le i_0 \le t$, to answer the following question in $O(|X|^2)$ time: is there a set of indices containing $i_0$ and satisfying R2? Starting from the set $\{i_0\}$, iterate the operator $I \mapsto I \cup \bigcup_{j \in I} \{j \in \{1, \dots, t\} \setminus I, \{x_i, y_j\} \in \mathcal{F}\}$ until stability, and let $I_0$ be the resulting set. Note that $I_0$ can be computed in $O(|X|^2)$ time. Moreover, any set containing $i_0$ and satisfying R2 must include $I_0$. If $I_0$ satisfies R2, which can be checked in $O(|X|^2)$ time, then the answer is positive. Otherwise, it means there exists a winning set of the form $\{x_i\}$ or $\{x_i, x_j\}$ with $i \in I_0$, therefore the answer is negative.

In conclusion, detecting whether R1 or R2 applies, and performing the reduction if so, can be done in $O(|X|^3)$ time. Obviously, at most $|X|$ such reductions can be performed in succession. When no reduction applies anymore, Claim 3 concludes: if at least one winning set remains, then Maker wins, otherwise Breaker trivially wins. $\square$

## A.4 Posets of height 2, winning sets of size 1 in Maker-Maker convention

We establish PSPACE-completeness, in the Maker-Maker convention, for a family of poset positional games which Theorem 4 has shown to be solved in polynomial time in the Maker-Breaker convention.

**Theorem 18.** For poset positional games in the Maker-Maker convention, deciding whether the first (resp. second) player has a winning strategy is PSPACE-complete, even when restricted to instances where: the poset is of height 2, all the winning sets are of size 1, and all the nonminimal elements are winning sets.

*Proof.* We perform a reduction from AVOID TRUE, which is defined as follows. Given a 2-POSDNF formula $\phi$ on a set of variables $V$, two players, Alice and Bob, alternately choose a variable in $V$ (which has not been chosen yet) and set it to True, until one of the clauses of $\phi$ is satisfied. The player who first turns $\phi$ to True loses. Note that no draw is possible. Deciding the outcome of AVOID TRUE has been proved to be PSPACE-complete by Schaefer [14].

Let $(V, \phi)$ be an instance of AVOID TRUE. Denote by $x_1, \dots, x_n$ the variables in $V$ and by $C_1, \dots, C_m$ the clauses of $\phi$. We build a poset positional game $\mathcal{G} = (X, \mathcal{F}, P)$ as follows:

* For each variable $x_i \in V$, we add a vertex $v_i$ in $X$.

* For each clause $C_j \in \phi$, we add a vertex $u_j$ in $X$ and the winning set $\{u_j\}$ in $\mathcal{F}$.

* For each variable $x_i \in C_j$, we add $v_i < u_j$ in $P$.

We prove that the first player in AVOID TRUE has a winning strategy in $(V, \phi)$ if and only if the first player in $\mathcal{G}$ has a winning strategy (which is equivalent to the second player in $\mathcal{G}$ not having a winning strategy, since no draw will be possible in $\mathcal{G}$).

We will name the players Alice and Bob in both games. By symmetry, suppose Alice has a winning strategy $S$ in AVOID TRUE, going first (resp. second). We define a strategy for her in $\mathcal{G}$ as follows. Alice considers that any vertex $v_i$ being claimed corresponds to the variable $x_i$ being set to True in AVOID TRUE. Whenever it is Alice's turn, she claims the vertex $v_i$ corresponding to the variable $x_i$ that she would have set to True according to $S$. Since $S$ is a winning strategy for Alice, Bob will be the first in AVOID TRUE to set some variable $x_i$ to True which turns a clause $C_j$ to True. This means that $v_i$ is the last predecessor of $u_j$ in $\mathcal{G}$. Therefore, Alice simply claims $u_j$ to win. $\square$