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.
In some games, it is possible to partition the elements of X (or a subset of them) into a set of pairwise-disjoint pairs.
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.
Hence: Paul Erdős and John Selfridge presented a general condition that guarantees Breaker a winning strategy.
Whenever Maker takes an element, the potential of every set containing it increases to
; whenever Breaker takes an element, the potential of every set containing it drops to 0, i.e., decreases by
To every element, we assign a value which equals the total potential-increase in case Maker takes it, i.e.,
This guarantees that, from the first turn of Breaker onwards, the potential always weakly decreases.
In Maker's first turn, he can, at most, double the potential (by taking an element contained in all winning-sets).
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.
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
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.
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
Therefore, if we consider only the winning-sets that were touched once, the potential-sum weakly increases.
is the smallest number of colors needed to color the elements of X such that no single set in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.")
[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.
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).
Erdos proved already in 1963, using the probabilistic method, that such a coloring exists whenever the number of hyperedges is less than
, where r(E) is the number of elements Maker has to take in order to win it.
[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
So Breaker needs to own a fraction larger than (1-t) of the points in every set.
, 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.