Biased positional game

Biased positional game

A biased positional game is a variant of a positional-game. Like most positional games, it is described by a set of positions/points/elements (<math>X</math>) and a family of subsets (<math>\mathcal{F}</math>), 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: *'

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 <math>d_2</math>. This condition can be generalized to biased games as follows: In particular, in the unbiased game the condition becomes <math>\sum_{E\in \mathcal{F}} 2^{1-|E|} < 1</math>. If the graph is k-uniform, the condition becomes <math>|\mathcal{F}| < (1+1/p)^{k-1}</math>. It is remarkable that this condition does not depend on q at all. **If each winning-set has at most k elements, and <math>\sum_{E\in \mathcal{F}} \left(1+{q\over p k}\right)^{p-|E|} < 1</math>, then Avoider wins (p:q) game when playing first.''

See also * [[box-making-game]]

References