Biased positional game

A biased positional game^{[1][2]: 27–42} is a variant of a positional game. Like most positional games, it is described by a set of positions/points/elements (${\displaystyle X}$) and a family of subsets (${\displaystyle {\mathcal {F}}}$), which are usually called the winning-sets. It is played by two players who take turns picking elements until all elements are taken. While in the standard game each player picks one element per turn, in the biased game each player takes a different number of elements.

More formally, for every two positive integers p and q, a (p:q)-positional game is a game in which the first player picks p elements per turn and the second player picks q elements per turn.

The main question of interest regarding biased positional games is what is their threshold bias - what is the bias in which the winning-power switches from one player to the other player.

Example

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.

A winning condition for Breaker

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]

A winning condition for Maker

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.

A winning condition for Avoider

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]

See also

• Box-making game

References

This page was last edited on 3 January 2023, at 23:24