Maker-Breaker game

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, Maker 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.

There has been quite some research 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 the 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) 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 an advantage: 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

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

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

Paul Erdős and John Selfridge presented a general condition that guarantees Breaker a winning strategy.[6] 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 Erdos-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 Erdos-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}}$.[6]

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.

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.[8]^{: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.

Summary table

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[6]	${\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[7]
Pair-degree d2, ${\displaystyle |{\mathcal {F}}|>2^{k-3}\cdot d_{2}\cdot |X|}$	Maker[8]		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}}$ (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?

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