Игра в несоответствие

Игра на несоответствие — это разновидность позиционной игры . Как и большинство позиционных игр, она описывается своим набором позиций/точек/элементов ( ) и семейством наборов ( - семейством подмножеств ) . В нее играют два игрока, называемые Balancer и Unbalancer . Каждый игрок по очереди выбирает элемент. Цель Balancer — гарантировать, что каждый набор в сбалансирован, т. е. элементы в каждом наборе распределены примерно поровну между игроками. Цель Unbalancer — гарантировать, что по крайней мере один набор не сбалансирован. ${\displaystyle X}$${\displaystyle {\mathcal {F}}}$${\displaystyle X}$${\displaystyle {\mathcal {F}}}$

Формально цель балансировщика определяется вектором , где n — число наборов в . Балансировщик побеждает, если в каждом наборе i разница между числом элементов, принимаемых Балансировщиком, и числом элементов, принимаемых Небалансировщиком, не превышает b _i . ${\displaystyle (b_{1},\ldots ,b_{n})}$${\displaystyle {\mathcal {F}}}$

Эквивалентно, мы можем представить, что Balancer помечает каждый элемент значением +1, а Unbalancer помечает каждый элемент значением -1, а цель Balancer — гарантировать, что абсолютное значение суммы меток в наборе i не превышает b _i .

Игра была введена Фризе, Кривелевичем, Пихурко и Сабо ^[1] и обобщена Алоном, Кривелевичем, Спенсером и Сабо ^{[2] .}

В игре Maker-Breaker , Breaker должен взять хотя бы один элемент из каждого набора.

В игре Avoider-Enforcer Avoider должен взять не более k-1 элемента в каждом наборе с k вершинами.

В игре на несоответствие Балансировщик должен достичь обеих целей одновременно: он должен взять по крайней мере определенную долю и по крайней мере определенную долю элементов в каждом наборе.

Пусть n — число наборов, а k _i — число элементов в наборе i .

• Если , то у Balancer есть выигрышная стратегия. В частности, если для всех i , , то у Balancer есть выигрышная стратегия. В частности, если размер всех наборов равен k , то Balancer может гарантировать, что в каждом наборе каждый из игроков имеет от и элементов. ^[2]${\displaystyle \sum _{i=1}^{n}\exp \left({-b_{i}^{2} \over 2k_{i}}\right)\leq 1/2}$${\displaystyle b_{i}\geq {\sqrt {2k_{i}\ln(2n)}}}$${\displaystyle {k \over 2}-{\sqrt {k\ln(2n)/2}}}$${\displaystyle {k \over 2}+{\sqrt {k\ln(2n)/2}}}$
• Если , то у Balancer есть выигрышная стратегия для случая, когда для каждого i , b _i = k _i -1 (поэтому Balancer может, чтобы каждый игрок имел элемент в каждом из множеств). ^[1]${\displaystyle \sum _{i=1}^{n}2^{-k_{i}}<1/4}$