Maker-Breaker game

In combinatorial game theory, Maker-Breaker games are a subclass of positional games introduced by Paul Erdős and John Selfridge.

It is a two-person game with complete information played on a hypergraph (V,H) where V is an arbitrary set (called the board of the game) and H is a family of subsets of V, called the winning sets. The two players alternately occupy previously unoccupied elements of V.

The first player, Maker, has to occupy a winning set to win; and the second player, Breaker, has to stop Maker from doing so; if Breaker successfully prevents maker from occupying a winning set to the end of the game, then Breaker wins. Thus, in a Maker–Breaker positional game, Maker wins if he occupies all elements of some winning set and Breaker wins if he prevents Maker from doing so. There can be no draw in a Maker-Breaker positional game: one player always wins.

Erdős and Selfridge proved that, when the winning sets are large and the number of winning sets is small, Breaker can always win. More precisely, if the winning sets are all of size [math]\displaystyle{ k }[/math], and the number of winning sets is less than [math]\displaystyle{ 2^k-1 }[/math], then Breaker has a winning strategy. On the other hand, they provide examples of Maker-Breaker games where the number of winning sets is exactly [math]\displaystyle{ 2^k-1 }[/math] and where Maker can force a win.

Infinite boards

The definition of Maker-Breaker game has a subtlety when there are infinitely many vertices ([math]\displaystyle{ |V|=\infty }[/math]) and infinitely many winning sets ([math]\displaystyle{ |H|=\infty }[/math]). 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.

Comparison with tictactoe

When tictactoe is played as a Maker–Breaker positional game, Maker has a winning strategy. This difference from tictactoe arises because, in tictactoe, when the second player (Breaker) takes two squares in a line, the first player (Maker) must respond to the threat by blocking the line. This forced response may be used to divert Maker from getting a winning line. In the corresponding Maker-Breaker game, Maker can ignore these threats, because getting three in a row first is not a winning condition for Breaker.

Maker-Breaker games on graphs

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