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

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

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

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

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

Сравнение с другими играми

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

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

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

Условия победы

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

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

Ссылки

^ Jump up to: ^а ^б Фриз, Алан; Кривелевич, Михаил; Пихурко Олег; Сабо, Тибор (2005). «Игра в Ералаш» . Комбинаторика, теория вероятностей и вычисления . 14 (5–6): 783–793. дои : 10.1017/S0963548305006851 . ISSN 1469-2163 . S2CID 16104089 .
^ Jump up to: ^а ^б Алон, Нога; Кривелевич, Михаил; Спенсер, Джоэл; Сабо, Тибор (29 сентября 2005 г.). «Игры на противоречия» . Электронный журнал комбинаторики . 12 (1): 51. дои : 10.37236/1948 . ISSN 1077-8926 .

[Frieze_2005-1] Jump up to: ^а ^б Фриз, Алан; Кривелевич, Михаил; Пихурко Олег; Сабо, Тибор (2005). «Игра в Ералаш» . Комбинаторика, теория вероятностей и вычисления . 14 (5–6): 783–793. дои : 10.1017/S0963548305006851 . ISSN 1469-2163 . S2CID 16104089 .

[Alon_2005-2] Jump up to: ^а ^б Алон, Нога; Кривелевич, Михаил; Спенсер, Джоэл; Сабо, Тибор (29 сентября 2005 г.). «Игры на противоречия» . Электронный журнал комбинаторики . 12 (1): 51. дои : 10.37236/1948 . ISSN 1077-8926 .

[ 1 ]

[ 2 ]