Maker-Breaker game

A Maker-Breaker game is a kind of positional game.^{[1]: 13–24} Like most positional games, it is described by its set of positions/points/elements (${\displaystyle X}$) and its family of winning-sets (${\displaystyle {\mathcal {F}}}$- a family of subsets of ${\displaystyle X}$). It is played by two players, called Maker and Breaker, who alternately take previously untaken elements.

In a Maker-Breaker game, Maker wins if he manages to hold all the elements of a winning-set, while Breaker wins if he manages to prevent this, i.e. to hold at least one element in each winning-set. Draws are not possible. In each Maker-Breaker game, either Maker or Breaker has a winning strategy. The main research question about these games is which of these two options holds.

A classic Maker-Breaker game is Hex. There, the winning-sets are all paths from the left side of the board to the right side. Maker wins by owning a connected path; Breaker wins by owning a connected path from top to bottom, since it blocks all connected paths from left to right.

Tic-tac-toe can be played as a Maker-Breaker game: in that variant, the goal of Maker is to pick 3 squares in a row, and the goal of Breaker is just to prevent Maker from doing so. In that variant, Breaker has a winning strategy. This is in contrast to the classic variant (which is a Strong positional game) where the second player has a drawing strategy (see Strong positional game#Comparison to Maker-Breaker game).

Unordered CNF Game^[2] on a positive CNF (all positive literals) can be considered as a Maker-Breaker game where Maker wants to falsify the CNF, and Breaker wants to satisfy it.

Some research has been done on playing Maker-Breaker games when the board of the game is the edge set ${\displaystyle E}$ of some graph ${\displaystyle G}$ (usually taken as a complete graph), and the family of winning-sets is ${\displaystyle {\mathcal {F}}=\{E'\subset E\vert G[E']{\hbox{ has property }}{\mathcal {P}}\}}$, where ${\displaystyle {\mathcal {P}}}$ is some graph property (usually taken to be monotone increasing [clarify?]) such as connectivity.^[3] For instance, the Shannon switching game is a Maker-Breaker game in which the winning sets are the paths between two distinguished vertices.

In a Maker-Breaker game, usually Maker plays first. But it is also possible to let Breaker play first. Playing first is always advantageous: any winning strategy for Maker playing second on ${\displaystyle (X,{\mathcal {F}})}$ yields a winning strategy for Maker playing first on ${\displaystyle (X,{\mathcal {F}}).}$ The same is true for Breaker.^[1]: 15

Moreover, for every game ${\displaystyle (X,{\mathcal {F}})}$ we can define its transversal game ${\displaystyle (X,{\mathcal {F^{*}}})}$, in which the winning-sets are the minimal sets touching each winning-set in the original game. For example, if in the original game the winning-sets are { {1,2,3},{4,5,6} } then in the dual game they are { {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6} }. Then, the winning strategies for Breaker playing first on ${\displaystyle (X,{\mathcal {F}})}$ are exactly the winning-strategies for Maker playing first on ${\displaystyle (X,{\mathcal {F^{*}}})}$.^[4]: 2

Furthermore, there is an alternative Misère convention of a Maker-Breaker game called an Avoider-Enforcer game.

Maker-Breaker game is PSPACE-complete even if the size of each set is restricted to 6.^[5] The first result was from 1978 where the size of each set was restricted to 11,^[6] where the game was mentioned as ${\displaystyle G}$(POS CNF 11).

Several kinds of strategies are commonly used to solve Maker-Breaker games.

In some games, it is possible to partition the elements of X (or a subset of them) into a set of pairwise-disjoint pairs. Under certain conditions, a player can win using the following greedy strategy: "whenever your opponent picks an element of pair i, pick the other element of pair i".

The "certain conditions" are different for Maker and for Breaker; see pairing strategy.

Every winning-strategy for First in a strong positional game, is also a winning strategy for Maker in the maker-breaker variant (see Strong positional game#Comparison to Maker-Breaker game). In particular, if in the strong-positional variant there can be no draw, then in the maker-breaker variant Maker has a winning strategy. The opposite is not necessarily true: a winning-strategy for Maker in the maker-breaker variant is not necessarily a winning-strategy for First in the strong variant, since in the strong variant, Second can win by claiming a winning-set before First.

In contrast, every winning-strategy for Breaker in a maker-breaker game, is also a drawing-strategy for Second in the strong-positional variant.

Suppose we can find a function that assigns, to each winning-set, a potential based on the number of elements already taken from it by Maker/Breaker. The potential function should satisfy the following properties:

• The potential of a winning-set is between 0 and 1;
• When Breaker takes an element, the potential of all sets containing it drops to 0 and remains 0;
• When Maker takes an element, the potential of all (non-broken) sets containing it increases;
• The potential of a set owned by Maker is 1.

Then, Maker wins iff the potential-sum is more than 0, and Breaker wins iff the potential-sum is less than 1. Hence:

• If the initial sum is more than 0, and Maker can play such that the potential-sum weakly increases, then this is a winning strategy for Maker;
• If the initial sum is less than 1, and Breaker can play such that the potential-sum weakly decreases, then this is a winning strategy for Breaker.

Paul Erdős and John Selfridge presented a general condition that guarantees Breaker a winning strategy.^[7] They used a potential-based strategy. They defined the potential of any (non-broken) winning-set ${\displaystyle E}$ with ${\displaystyle |E|}$ unoccupied vertices as ${\displaystyle 2^{-|E|}}$. So the potential of a set occupied by Maker is indeed ${\displaystyle 2^{-0}=1}$. Whenever Maker takes an element, the potential of every set containing it increases to ${\displaystyle 2^{-(|E|-1)}}$, i.e., increases by ${\displaystyle 2^{-|E|}}$; whenever Breaker takes an element, the potential of every set containing it drops to 0, i.e., decreases by ${\displaystyle 2^{-|E|}}$. To every element, we assign a value which equals the total potential-increase in case Maker takes it, i.e., ${\displaystyle w(v):=\sum _{v\in E}2^{-|E|}}$. The winning strategy of Breaker is pick an element with a highest value. This guarantees that, from the first turn of Breaker onwards, the potential always weakly decreases. Hence, if the potential at the first Breaker turn is less than 1, Breaker wins. In Maker's first turn, he can, at most, double the potential (by taking an element contained in all winning-sets). Therefore, it is sufficient that, at the game start, the potential is less than 1/2. To summarize, the Erdős-Selfridge theorem says that:

If ${\displaystyle \sum _{E\in {\mathcal {F}}}2^{-|E|}<1/2}$, then ${\displaystyle {\mathcal {F}}}$ is Breaker's win.

The theorem gives a very easy-to-check condition, and when this condition is satisfied, it also gives an efficient algorithm for computing Breaker's optimal strategy.

The potential function has a probabilistic interpretation. The potential of a winning-set is the probability that, if the game is played randomly from now on, Maker will own that set. The potential-sum is thus the expected number of winning-sets owned by Maker if the game is played randomly. Whenever the potential-sum is less than 1, there must be a way to play the game such that the number of sets owned by Maker is 0. By ensuring that the potential-sum remains below 1, Breaker essentially de-randomizes this probabilistic claim until at the end of the game, it becomes a certainty.

Note that if Breaker plays first, the condition changes to ${\displaystyle \sum _{E\in {\mathcal {F}}}2^{-|E|}<1}$.

In particular, if the winning-sets are all of size k (i.e., the game-hypergraph is k-uniform), then the Erdős-Selfridge theorem implies that Breaker wins whenever ${\displaystyle |{\mathcal {F}}|<2^{k-1}}$, i.e., the number of winning-sets is less than ${\displaystyle 2^{k-1}}$.^[7]

The number ${\displaystyle 2^{k-1}}$ is tight: there are ${\displaystyle k}$-uniform hypergraphs where the number of winning sets is exactly ${\displaystyle 2^{k-1}}$, and where Maker has a winning strategy. For example, consider a perfect binary tree of height ${\displaystyle k-1}$. It has ${\displaystyle 2^{k-1}}$ leaves. Define V as the set of tree nodes, and H as the family of all ${\displaystyle 2^{k-1}}$ paths from the root to a leaf. Maker starts by picking the root. Then, if Breaker picks an element in the left subtree, Maker picks the root of the right subtree, and vice versa. By continuing this way, Maker can always pick a full path, i.e., a winning-set.

If all winning-sets are pairwise-disjoint and their size is at least 2, then Breaker can win using a pairing strategy.

Suppose now that the winning-sets are almost disjoint, i.e., any two winning-sets have at most one element in common. If all winning-sets are of size ${\displaystyle k}$, and the number of winning sets is less than ${\displaystyle 4^{k-c{\sqrt {k}}}}$(for some fixed constant c), then Breaker has a winning strategy.^[8] So this situation is easier for Breaker than the general case, but harder than the case of disjoint winning-sets.

Define the degree of a set of elements as the number of different winning-sets that contain this set. Define the pair-degree of a set-family, denoted ${\displaystyle d_{2}}$, as the maximum degree of a pair of elements (maximum over all pairs). If all winning-sets are of size ${\displaystyle k}$, and the number of winning-sets is more than ${\displaystyle 2^{k-3}\cdot d_{2}\cdot |X|}$, then Maker has a winning strategy.^{[9]: Theorem 1}

The strategy uses the same potential function used by Erdos and Selfridge: the potential of a winning-set ${\displaystyle E}$ with ${\displaystyle |E|}$ unoccupied elements (and no element occupied by Breaker) is ${\displaystyle 2^{-|E|}}$. The value of an element is the total potential-decrease if Breaker takes that element, which is the same as the total potential-increase if Maker takes it. Maker's strategy is simply to take the highest-value element.

Whenever Maker takes an element, the potential of every winning-set that contains it increases by ${\displaystyle 2^{-|E|}}$; whenever Breaker takes an element, the potential of every set that contains it and does not contain Maker's element decreases by ${\displaystyle 2^{-|E|}}$. Therefore, if we consider only the winning-sets that were touched once, the potential-sum weakly increases. The potential-sum can decrease only due to sets that contain both Maker's element and Breaker's element. These sets gain ${\displaystyle 2^{-|E|}}$ but then lose ${\displaystyle 2^{-(|E|-1)}}$, so all in all they lose ${\displaystyle 2^{-|E|}}$. Since such sets have at least two elements, each such set loses at most 1/4. By the limited-pair-degree assumption, the number of such sets is at most d₂. Hence, after each round the potential-sum drops by at most d₂/4. The number of rounds is |X|/2, so the final potential is smaller than the initial potential by at most ${\displaystyle d_{2}\cdot |X|/8}$. The initial potential is ${\displaystyle |{\mathcal {F}}|\cdot 2^{-k}}$.

If ${\displaystyle |{\mathcal {F}}|\cdot 2^{-k}>d_{2}\cdot |X|/8}$, the final potential is more than 0, so there is at least one winning-set with potential 1. This set is owned by Maker.

The chromatic number of ${\displaystyle {\mathcal {F}}}$ is the smallest number of colors needed to color the elements of X such that no single set in ${\displaystyle {\mathcal {F}}}$ is monochromatic. If the chromatic number of ${\displaystyle {\mathcal {F}}}$ is 3, then Maker has a winning-strategy.^[10]

The following table summarizes some conditions that guarantee that one of the players has a winning strategy. The condition in the "tightness" column indicates when specific hypergraphs are known on which the strategy stops working.

In all conditions, k is the size of winning-sets (i.e., the game hypergraph is k-uniform).

Condition	Winner	Tightness	Comments
${\displaystyle |{\mathcal {F}}|<2^{k-1}}$	Breaker[7]	${\displaystyle |{\mathcal {F}}|\geq 2^{k-1}}$	Potential strategy
Disjoint winning-sets, size at least 2	Breaker		Pairing strategy
Almost-disjoint sets, ${\displaystyle |{\mathcal {F}}|<4^{k-c{\sqrt {k}}}}$	Breaker[8]
Pair-degree d2, ${\displaystyle |{\mathcal {F}}|>2^{k-3}\cdot d_{2}\cdot |X|}$	Maker[9]		Potential strategy

It is possible to play a game in which both players want to attain the goal of Breaker (i.e., have at least one element in each winning-set). Then, the game is not necessarily zero-sum - it is possible that both players will win. In fact, whenever Breaker has a winning strategy in the Maker-Breaker game, it is possible that two Breakers will both win in the Breaker-Breaker game.

An application of this strategy is an efficient algorithm for coloring a hypergraph. Suppose we want to color the vertices of a k-uniform hypergraph in two colors such that in each hyperedge, both colors are represented. Erdos proved already in 1963, using the probabilistic method, that such a coloring exists whenever the number of hyperedges is less than ${\displaystyle 2^{k-1}}$, in other words, a hypergraph must be 2-uniform for such a coloring to exist. (see Property B). However, the proof was not constructive. Using Breaker's constructive winning strategy, we can color the hypergraph ${\displaystyle {\mathcal {F}}}$ by letting two Breakers play one against the other with their winning strategies. Both players will win - so each player will have at least one vertex in every hyperedge.^{[1]: 17–20}

Suppose that, in order to win, Maker does not need to occupy an entire winning-set - he only needs to own a part of such a set. When can Breaker win in this case?

m elements in one set (where Breaker does not own any element). If the size of each winning-set is at least m, and the number of sets is less than ${\displaystyle 2^{m-1}}$, then Breaker still has a winning strategy. The strategy uses a potential function: the potential of a "broken" set is 0, and the potential of a non-broken set E is ${\displaystyle 2^{-r(E)}}$, where r(E) is the number of elements Maker has to take in order to win it. So the initial potential of every winning-set is ${\displaystyle 2^{-m}}$, and the potential of a set occupied by Maker is 1. From here the proof is the same as the Erdos-Selfridge theorem.^{[9]: Lemma 1}

Suppose that, in order to win, Maker needs to own only a fraction t of the elements in one winning-set, where ${\displaystyle 1/2<t\leq 1}$. So Breaker needs to own a fraction larger than (1-t) of the points in every set. Define the constant: ${\displaystyle c_{t}:=(2t)^{t}\cdot (2-2t)^{1-t}=2\cdot t^{t}\cdot (1-t)^{1-t}}$(in the standard variant, ${\displaystyle t=1,c_{t}\to 2}$).

• If ${\displaystyle \sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<1}$, then Breaker has a winning strategy when playing first.^{[9]: Lemma 3}
• If ${\displaystyle \sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<{1 \over 2-2t}}$, then Breaker has a winning strategy when playing second.^[11]

In particular, if all sets are of size k and their number is less than ${\displaystyle {c_{t}}^{k}}$, then Breaker (playing first) has a winning strategy.

The strategy uses a potential function. The potential of a winning-set is defined as ${\displaystyle (2t)^{-r}(2-2t)^{-s}}$, where r is the number of elements Maker needs to take in order to occupy the set, and s is the number of elements Breaker needs to take in order to break it. If Maker occupies a set, then its potential will at some point be at least 1. Therefore, Breaker wins if he manages to keep the potential-sum below 1. Breaker's strategy is to take the element with the highest value, defined as the sum of potentials of winning-sets containing that element.

Whenever Maker takes an element, the potential of every set containing it is multiplied by 2t, so it increases by (2t-1) times the current potential. Whenever Breaker takes an element, the potential of every set containing it is multiplied by (2-2t), so it increases by (1-2t) times the current potential. Whenever Breaker and Maker both touch the same set, its potential is multiplied by 2t(2-2t), so it increases by -(2t-1)² times the current potential. Since Breaker's element has a highest value, the potential-sum always decreases. Therefore, if the initial potential-sum is less than 1, Breaker wins.

The definition of Maker-Breaker game has a subtlety when there are infinitely many vertices (${\displaystyle |V|=\infty }$) and infinitely many winning sets (${\displaystyle |H|=\infty }$). In this case we say that Breaker has a winning strategy if, for all j > 0, Breaker can prevent Maker from completely occupying a winning set by turn j.

• Clique game
• Arithmetic progression game
• Biased positional game
• Avoider-Enforcer game