Discrepancy Game

A discrepancy game is a kind of positional game. Like most positional games, it is described by its set of ''positions/points/elements'' ($X$) and a family of ''sets'' ($\mathcal$- a family of subsets of $X$). It is played by two players, called ''Balancer'' and ''Unbalancer''. Each player in turn picks an element. The goal of Balancer is to ensure that every set in $\mathcal$ is balanced, i.e., the elements in each set are distributed roughly equally between the players. The goal of Unbalancer is to ensure that at least one set is unbalanced.

Formally, the goal of balancer is defined by a vector $(b_1,\ldots,b_n)$ where ''n'' is the number of sets in $\mathcal$. Balancer wins if in every set ''i'', the difference between the number of elements taken by Balancer and the number of elements taken by Unbalancer is at most ''b_i''.

Equivalently, we can think of Balancer as labeling each element with +1 and Unbalancer labeling each element with -1, and Balancer's goal is to ensure the absolute value of the sum of labels in set i is at most ''b_i''.

The game was introduced by Frieze, Krivelevich, Pikhurko and Szabo, and generalized by Alon, Krivelevich, Spencer and Szabo.

Comparison to other games

In a Maker-Breaker game, Breaker has to take ''at least one'' element in every set.

In an Avoider-Enforcer game, Avoider has to take ''at most k-1'' element in every set with ''k'' vertices.

In a discrepancy game, Balancer has to attain both goals simultaneously: he should take at least a certain fraction, and at most a certain fraction, of the elements in each set.

Winning conditions

Let ''n'' be the number of sets, and ''k_i'' be the number of elements in set ''i''.

* If $\sum_^n \exp\left(\right) \leq 1/2$, then Balancer has a winning strategy. In particular, if for all ''i'', $b_i \geq \sqrt$, then Balancer has a winning strategy. In particular, if the size of all sets is ''k'', then Balancer can ensure that in each set, each of the players has between $- \sqrt$ and $+\sqrt$ elements.
* If $\sum_^n 2^ < 1/4$, then Balancer has a winning-strategy for the case that for every ''i'', ''b_i'' = ''k_i''-1 (so Balancer can each player has an element in each of the sets).

References

{{Reflist
Positional games