Игра «Официант–Клиент»

Игра Waiter-Client [1] (также называемая: [2] Picker-Chooser game ) — это разновидность позиционной игры . Как и большинство позиционных игр, она описывается своим набором позиций/очков/элементов ( ), и своим семейством выигрышных наборов ( - семейство подмножеств ). В нее играют два игрока, называемые Waiter и Client. В каждом раунде Waiter выбирает два элемента, Client выбирает один элемент, а Waiter получает другой элемент (аналогично протоколу Divide and Choose ). Х {\displaystyle X} Ф {\displaystyle {\mathcal {F}}} Х {\displaystyle X}

В игре Waiter-Client, Waiter выигрывает, если ему удается занять все элементы выигрышного набора, в то время как Client выигрывает, если ему удается предотвратить это, т. е. удержать хотя бы один элемент в каждом выигрышном наборе. Таким образом, Waiter и Client имеют, соответственно, те же цели, что Maker и Breaker в игре Maker-Breaker ; отличаются только правила взятия элементов.

В игре «Клиент-Ожидатель» условия выигрыша меняются местами: Клиент выигрывает, если ему удается удержать все элементы выигрышного набора, а Ожидатель выигрывает, если ему удается удержать хотя бы один элемент в каждом выигрышном наборе.

Сравнение с играми Maker-Breaker

В некоторых случаях Waiter гораздо сильнее игрока с той же целью в варианте Maker-Breaker. Например, рассмотрим вариант игры в крестики-нолики , в котором Maker выигрывает, заняв k клеток в ряду, а Breaker выигрывает, заблокировав все ряды.

Затем, когда доска бесконечна, Waiter может выиграть как Maker для любого k >= 1. [ 3] Более того, Waiter может выиграть как Breaker для любого k >= 2: в каждом раунде Waiter выбирает пару квадратов, которые не являются смежными с парами, выбранными до сих пор (например, в раунде i он выбирает квадраты (2 i ,0) и (2 i ,1)). Более того, даже когда доска конечна, Waiter всегда выигрывает как Breaker, когда k >= 8. [4]

Это приводит к следующей гипотезе Йожефа Бека : [2] Если Maker выигрывает игру Maker-Breaker на , играя вторым, то Waiter выигрывает игру Waiter-Client на . Аналогично, если Breaker выигрывает игру Maker-Breaker на , играя вторым, то Waiter выигрывает игру Client-Waiter на . ( Х , Ф ) {\displaystyle (X,{\mathcal {F}})} ( Х , Ф ) {\displaystyle (X,{\mathcal {F}})} ( Х , Ф ) {\displaystyle (X,{\mathcal {F}})} ( Х , Ф ) {\displaystyle (X,{\mathcal {F}})}

Особые случаи

k-однородные гиперграфы

Предположим, что все выигрышные наборы имеют размер k (т.е. игровой гиперграф является k -однородным). В игре Maker-Breaker теорема Эрдеша-Селфриджа подразумевает, что Breaker выигрывает, если количество выигрышных наборов меньше . [5] 2 к − 1 {\displaystyle 2^{k-1}}

Согласно вышеизложенной гипотезе, мы ожидаем, что то же самое будет иметь место в соответствующей игре Клиент-Ожидатель - Ожидающий "должен" победить (как Разрушитель), когда количество выигрышных наборов меньше . Однако в настоящее время известны только следующие более слабые границы: 2 к − 1 {\displaystyle 2^{k-1}}

  • Официант выигрывает, если количество выигрышных сетов меньше . [1] 2 к − 1 8 ( к + 1 ) {\displaystyle {2^{k-1} \over 8(k+1)}}
  • Официант выигрывает, если количество выигрышных сетов меньше . [4] 2 к − 1 3 к + 1 / 2 {\displaystyle {2^{k-1} \over 3{\sqrt {k+1/2}}}}

Ссылки

  1. ^ ab Хефец, Дэн; Кривелевич, Майкл; Тан, Вэй Эн (2017). «Ожидающе-клиентские и клиентско-ожидающие гамильтоновости игры на случайных графах». European Journal of Combinatorics . 63 : 26–43 . arXiv : 1509.05356 . doi : 10.1016/j.ejc.2017.02.002. ISSN  0195-6698. S2CID  11084208.
  2. ^ ab Бек, Йожеф (2002-04-01). «Позиционные игры и метод второго момента». Combinatorica . 22 (2): 169– 216. doi :10.1007/s004930200009. ISSN  0209-9683. S2CID  7005199.
  3. ^ Бек, Йожеф (2005). «Позиционные игры». Комбинаторика, вероятность и вычисления . 14 ( 5– 6): 649– 696. doi :10.1017/S0963548305007078. ISSN  1469-2163. S2CID  27877713.
  4. ^ аб Черненски, Андраш; Мандити, К. Иветт; Плухар, Андраш (2009). «О позиционных играх Селектор – Пикер». Дискретная математика . 309 (16): 5141–5146 . doi : 10.1016/j.disc.2009.03.051 . ISSN  0012-365X.
  5. ^ Эрдёш, П.; Селфридж , Дж. Л. (1973). «О комбинаторной игре» (PDF) . Журнал комбинаторной теории . Серия A. 14 (3): 298– 301. doi : 10.1016/0097-3165(73)90005-8 . MR  0327313.
Взято с "https://en.wikipedia.org/w/index.php?title=Waiter–Client_game&oldid=1140625518"