Предвзятая позиционная игра - Biased positional game

А предвзятая позиционная игра^{[1][2]:27–42} это вариант позиционная игра. Как и большинство позиционных игр, она описывается набором позиции / точки / элементы (${\displaystyle X}$) и семейство подмножеств (${\displaystyle {\mathcal {F}}}$), которые обычно называют выигрышные наборы. В нее играют два игрока, которые по очереди выбирают элементы, пока не будут взяты все элементы. В то время как в стандартной игре каждый игрок выбирает один элемент за ход, в предвзятой игре каждый игрок берет разное количество элементов.

Более формально, для каждых двух положительных целых чисел п и q, (p: q) -позиционная игра - это игра, в которой первый игрок выбирает п элементов за ход, и второй игрок выбирает q элементов за оборот.

Главный интересующий вопрос относительно предвзятых позиционных игр - каковы их пороговое смещение - какова предвзятость, при которой сила выигрыша переключается с одного игрока на другого.

Пример

В качестве примера рассмотрим игра треугольник. В этой игре все элементы - это ребра полный график на п вершины, а выигрышные множества - все треугольники (= клики на 3 вершинах). Предположим, мы играем его как Maker-Breaker игра, то есть цель Maker (первого игрока) - взять треугольник, а цель Breaker (второй треугольник) - помешать Maker взять треугольник. Используя простой кейс-анализ, можно доказать, что у Maker всегда есть выигрышная стратегия. п составляет не менее 6. Поэтому интересно спросить, можно ли смещать это преимущество, позволяя Брейкеру выбирать более 1 элемента за ход.

Действительно, можно доказать, что:^[1]

• Для каждого ${\displaystyle q\leq 0.5{\sqrt {n}}}$, Maker выигрывает (1:q) игра треугольник на п вершины.
• Для каждого ${\displaystyle q\geq 2{\sqrt {n}}}$, Breaker выигрывает (1:q) игра треугольник на п вершины.

Выигрышное условие для Breaker

В непредвзятом Maker-Breaker игра, теорема Эрдоша-Селфриджа дает условие победы для Breaker. Это условие можно обобщить на предвзятые игры следующим образом:^{[3] [2]:30–32}

• Если ${\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p}<1}$, то у Брейкера есть выигрышная стратегия в игре (p: q), когда он играет первым.
• Если ${\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p}<{1 \over 1+q}}$, то у Брейкера есть выигрышная стратегия в игре (p: q), даже когда он играет вторым.

Стратегия использует потенциальную функцию, которая обобщает функцию Эрдоша-Селфриджа. Потенциал (неразрывного) выигрышного сета E с |E| непринятые элементы определяются как ${\displaystyle (1+q)^{-|E|/p}}$. Если Мейкер выигрывает игру, то существует набор E с |E| = 0, поэтому его потенциал равен 1; следовательно, чтобы доказать, что Брейкер побеждает, достаточно доказать, что окончательная потенциальная сумма меньше 1. В самом деле, по предположению, потенциальная сумма на первом ходу Брейкера меньше 1; и если Брейкер всегда выбирает элемент, который максимизирует падение потенциала, можно показать, что сумма потенциалов всегда слабо уменьшается.

Когда в каждом выигрышном сете ${\displaystyle k}$ элементы, для некоторых фиксированных k, Условие выигрыша Breaker упрощается до: ${\displaystyle |{\mathcal {F}}|<(q+1)^{k/p}}$ (при первой игре) или ${\displaystyle |{\mathcal {F}}|<(q+1)^{k/p-1}}$(при игре вторым). Это условие жесткое: есть k-унифицированные наборы-семейства с ${\displaystyle |{\mathcal {F}}|=(q+1)^{k/p-1}}$устанавливает, где Maker побеждает.^[4]

Выигрышное условие для Maker

В беспристрастной игре Maker-Breaker теорема Бека дает условие победы для Maker. Он использует парную степень гиперграфа, обозначаемую ${\displaystyle d_{2}}$. Это условие можно обобщить на предвзятые игры следующим образом:^[3]

Если ${\displaystyle \sum _{E\in {\mathcal {F}}}{p+q \over p}^{-|E|}>{p^{2}q^{2} \over (p+q)^{3}}\cdot d_{2}\cdot |X|}$, то у Maker есть выигрышная стратегия в игре (p: q), когда он играет первым.

Выигрышное условие для Avoider

В предвзятом Игра Avoider-Enforcer, следующие условия гарантируют, что у Avoider есть выигрышная стратегия:^[2]:47–49

• Если ${\displaystyle \sum _{E\in {\mathcal {F}}}(1+1/p)^{p-|E|}<1}$, то Avoider выигрывает игру (p: q), играя первым, как по строгому, так и по монотонному набору правил. Это почти сложно: существует бесконечное семейство (p: q) игр, в которых это выражение немного больше единицы, и Enforcer выигрывает.^[5] В частности, в беспристрастной игре условие принимает вид ${\displaystyle \sum _{E\in {\mathcal {F}}}2^{1-|E|}<1}$. Если график k-равномерно, условие становится ${\displaystyle |{\mathcal {F}}|<(1+1/p)^{k-1}}$. Примечательно, что это условие не зависит от q вообще.
• Если каждый выигрышный набор содержит не более k элементов и ${\displaystyle \sum _{E\in {\mathcal {F}}}\left(1+{q \over pk}\right)^{p-|E|}<1}$, то Avoider выигрывает (p: q) игру, играя первым.^[6]

Смотрите также

• Игра в изготовление коробок

Рекомендации

1. Chvátal, V .; Эрдеш, П. (1978). «Предвзятые позиционные игры». Анналы дискретной математики. 2 (C): 221–229. Дои:10.1016 / S0167-5060 (08) 70335-2. ISSN  0167-5060.
2. Хефец, Дэн; Кривелевич Михаил; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры. Обервольфахские семинары. 44. Базель: Birkhäuser Verlag GmbH. ISBN  978-3-0348-0824-8.
3. Бек, Дж. (1982). «Замечания по позиционным играм. I». Acta Mathematica Academiae Scientiarum Hungaricae. 40 (1–2): 65–71. Дои:10.1007 / bf01897304. ISSN  0001-5954.
4. "Экстремальные гиперграфы для смещенной теоремы Эрдеша-Селфриджа". Электронный журнал комбинаторики. 20 (1). 2013-05-02. ISSN  1077-8926.
5. Хефец, Дэн; Кривелевич Михаил; Сабо, Тибор (01.07.2007). «Avoider - Enforcer games». Журнал комбинаторной теории, серия А. 114 (5): 840–853. Дои:10.1016 / j.jcta.2006.10.001. ISSN  0097-3165.
6. Беднарска-Бжденга, Малгожата (12.01.2014). «Игры Avoider-Forcer на гиперграфах с малым рангом». Электронный журнал комбинаторики. 21 (1): 1–2. Дои:10.37236/3095. ISSN  1077-8926.