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 {F}}$ - 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 {F}}$ 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 {F}}$ . 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,[1] and generalized by Alon, Krivelevich, Spencer and Szabo.[2]

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 _{i=1}^{n}\exp \left({-b_{i}^{2} \over 2k_{i}}\right)\leq 1/2$ , then Balancer has a winning strategy. In particular, if for all i, $b_{i}\geq {\sqrt {2k_{i}\ln(2n)}}$ , 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 ${k \over 2}-{\sqrt {k\ln(2n)/2}}$ and ${k \over 2}+{\sqrt {k\ln(2n)/2}}$ elements.[2]
If $\sum _{i=1}^{n}2^{-k_{i}}<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).[1]

References

Frieze, Alan; Krivelevich, Michael; Pikhurko, Oleg; Szabó, Tibor (2005). "The Game of JumbleG". Combinatorics, Probability and Computing. 14 (5–6): 783–793. doi:10.1017/S0963548305006851. ISSN 1469-2163.
Alon, Noga; Krivelevich, Michael; Spencer, Joel; Szabó, Tibor (2005-09-29). "Discrepancy Games". The Electronic Journal of Combinatorics. 12 (1): 51. ISSN 1077-8926.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Frieze_2005-1] Frieze, Alan; Krivelevich, Michael; Pikhurko, Oleg; Szabó, Tibor (2005). "The Game of JumbleG". Combinatorics, Probability and Computing. 14 (5–6): 783–793. doi:10.1017/S0963548305006851. ISSN 1469-2163.

[Alon_2005-2] Alon, Noga; Krivelevich, Michael; Spencer, Joel; Szabó, Tibor (2005-09-29). "Discrepancy Games". The Electronic Journal of Combinatorics. 12 (1): 51. ISSN 1077-8926.