Biased positional game

As an example, consider the triangle game. In this game, the elements are all edges of a complete graph on n vertices, and the winning-sets are all triangles (=cliques on 3 vertices). Suppose we play it as a Maker-Breaker game, i.e., the goal of Maker (the first player) is to take a triangle and the goal of Breaker (the second player) is to prevent Maker from taking a triangle. Using a simple case-analysis, it can be proved that Maker has a winning strategy whenever n is at least 6. Therefore, it is interesting to ask whether this advantaged can be biased by letting Breaker pick more than 1 element per turn.

Indeed, it is possible to prove that:[1]

• For every ${\displaystyle q\leq 0.5{\sqrt {n}}}$, Maker wins the (1:q) triangle game on n vertices.
• For every ${\displaystyle q\geq 2{\sqrt {n}}}$, Breaker wins the (1:q) triangle game on n vertices.

In an unbiased Maker-Breaker game, the Erdos-Selfridge theorem gives a winning condition for Breaker. This condition can be generalized to biased games as follows:[3] [2]^: 30–32

• If ${\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p}<1}$, then Breaker has a winning-strategy in the (p:q) game when playing first.
• If ${\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p}<{1 \over 1+q}}$, then Breaker has a winning-strategy in the (p:q) game even when playing second.

The strategy uses a potential function which generalized the function of Erdos-Selfridge. The potential of a (non-broken) winning-set E with |E| untaken elements is defined as ${\displaystyle (1+q)^{-|E|/p}}$. If Maker wins the game then there exists a set E with |E|=0, so its potential is 1; therefore, to prove that Breaker wins, it is sufficient to prove that the final potential-sum is less than 1. Indeed, by assumption, the potential-sum at Breaker's first turn is less than 1; and if Breaker always picks an element that maximizes the potential-drop, it is possible to show that the potential-sum always weakly decreases.

When each winning-set has ${\displaystyle k}$ elements, for some fixed k, Breaker's winning condition simplifies to: ${\displaystyle |{\mathcal {F}}|<(q+1)^{k/p}}$ (when playing first) or ${\displaystyle |{\mathcal {F}}|<(q+1)^{k/p-1}}$(when playing second). This condition is tight: there are k-uniform set-families with ${\displaystyle |{\mathcal {F}}|=(q+1)^{k/p-1}}$sets where Maker wins.[4]

In an unbiased Maker-Breaker game, a theorem by Beck gives a winning condition for Maker. It uses the pair-degree of the hypergraph - denoted by ${\displaystyle d_{2}}$. This condition can be generalized to biased games as follows:[3]

If ${\displaystyle \sum _{E\in {\mathcal {F}}}{p+q \over p}^{-|E|}>{p^{2}q^{2} \over (p+q)^{3}}\cdot d_{2}\cdot |X|}$, then Maker has a winning-strategy in the (p:q) game when playing first.

In a biased Avoider-Enforcer game, the following conditions guarantee that Avoider has a winning strategy:[2]^: 47–49

• If ${\displaystyle \sum _{E\in {\mathcal {F}}}(1+1/p)^{p-|E|}<1}$, then Avoider wins the (p:q) game when playing first, under both the strict and the monotonic ruleset. This is almost tight: there is an infinite family of (p:q) games in which this expression is slightly larger than 1 and Enforcer wins.[5] In particular, in the unbiased game the condition becomes ${\displaystyle \sum _{E\in {\mathcal {F}}}2^{1-|E|}<1}$. If the graph is k-uniform, the condition becomes ${\displaystyle |{\mathcal {F}}|<(1+1/p)^{k-1}}$. It is remarkable that this condition does not depend on q at all.
• If each winning-set has at most k elements, and ${\displaystyle \sum _{E\in {\mathcal {F}}}\left(1+{q \over pk}\right)^{p-|E|}<1}$, then Avoider wins (p:q) game when playing first.[6]

• Box-making game