Waiter–Client game

A Waiter-Client game[1] (also called:[2] Picker-Chooser game) is a kind of positional game. Like most positional games, it is described by its set of positions/points/elements ( $X$ ), and its family of winning-sets ( ${\mathcal {F}}$ - a family of subsets of $X$ ). It is played by two players, called Waiter and Client. Each round, Waiter picks two elements, Client chooses one element and Waiter gets the other element (similarly to the Divide and choose protocol).

In a Waiter-Client game, Waiter wins if he manages to occupy all the elements of a winning-set, while Client wins if he manages to prevent this, i.e., hold at least one element in each winning-set. So Waiter and Client have, respectively, the same goals as Maker and Breaker in a Maker-Breaker game; only the rules for taking elements are different.

In a Client-Waiter game the winning conditions are reversed: Client wins if he manages to hold all the elements of a winning-set, while Waiter wins if he manages to hold at least one element in each winning-set.

Comparison to Maker-Breaker games

In some cases, the Waiter is much more powerful than the player with the same goal in the Maker-Breaker variant. For example, consider a variant of tic-tac-toe in which Maker wins by taking k squares in a row and Breaker wins by blocking all rows.

Then, when the board is infinite, Waiter can win as Maker for any k >= 1.[3] Moreover, Waiter can win as Breaker for any k >= 2: in each round, Waiter picks a pair of squares that are not adjacent to the pairs picked so far (for example, in round i he picks the squares (2i,0) and (2i,1)). Moreover, even when the board is finite, Waiter always wins as Breaker when k >= 8. [4]

This leads to the following conjecture by József Beck:[2] If Maker wins the Maker-Breaker game on $(X,{\mathcal {F}})$ when playing second, then Waiter wins the Waiter-Client game on $(X,{\mathcal {F}})$ . Similarly, if Breaker wins the Maker-Breaker game on $(X,{\mathcal {F}})$ when playing second, then Waiter wins the Client-Waiter game on $(X,{\mathcal {F}})$ .

Special cases

k-uniform hypergraphs

Suppose the winning-sets are all of size k (i.e., the game-hypergraph is k-uniform). In a Maker-Breaker game, the Erdos-Selfridge theorem implies that Breaker wins if the number of winning-sets is less than $2^{k-1}$ . [5]

By the above conjecture, we would expect the same to hold in the corresponding Client-Waiter game - Waiter "should" win (as Breaker) whenever the number of winning-sets is less than $2^{k-1}$ . However, currently only the following weaker bounds are known:

Waiter wins if the number of winning-sets is less than ${2^{k-1} \over 8(k+1)}$ .[1]
Waiter wins if the number of winning-sets is less than ${2^{k-1} \over 3{\sqrt {k+1/2}}}$ .[4]

References

Hefetz, Dan; Krivelevich, Michael; Tan, Wei En (2017). "Waiter–Client and Client–Waiter Hamiltonicity games on random graphs". European Journal of Combinatorics. 63: 26–43. arXiv:1509.05356. doi:10.1016/j.ejc.2017.02.002. ISSN 0195-6698. S2CID 11084208.
Beck, József (2002-04-01). "Positional Games and the Second Moment Method". Combinatorica. 22 (2): 169–216. doi:10.1007/s004930200009. ISSN 0209-9683. S2CID 7005199.
Beck, József (2005). "Positional Games". Combinatorics, Probability and Computing. 14 (5–6): 649–696. doi:10.1017/S0963548305007078. ISSN 1469-2163. S2CID 27877713.
Csernenszky, András; Mándity, C. Ivett; Pluhár, András (2009). "On Chooser–Picker positional games". Discrete Mathematics. 309 (16): 5141–5146. doi:10.1016/j.disc.2009.03.051. ISSN 0012-365X.
Erdős, P.; Selfridge, J. L. (1973). "On a combinatorial game" (PDF). Journal of Combinatorial Theory. Series A. 14 (3): 298–301. doi:10.1016/0097-3165(73)90005-8. MR 0327313.

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

[:1-1] Hefetz, Dan; Krivelevich, Michael; Tan, Wei En (2017). "Waiter–Client and Client–Waiter Hamiltonicity games on random graphs". European Journal of Combinatorics. 63: 26–43. arXiv:1509.05356. doi:10.1016/j.ejc.2017.02.002. ISSN 0195-6698. S2CID 11084208.

[:0-2] Beck, József (2002-04-01). "Positional Games and the Second Moment Method". Combinatorica. 22 (2): 169–216. doi:10.1007/s004930200009. ISSN 0209-9683. S2CID 7005199.

[3] Beck, József (2005). "Positional Games". Combinatorics, Probability and Computing. 14 (5–6): 649–696. doi:10.1017/S0963548305007078. ISSN 1469-2163. S2CID 27877713.

[:2-4] Csernenszky, András; Mándity, C. Ivett; Pluhár, András (2009). "On Chooser–Picker positional games". Discrete Mathematics. 309 (16): 5141–5146. doi:10.1016/j.disc.2009.03.051. ISSN 0012-365X.

[es-5] Erdős, P.; Selfridge, J. L. (1973). "On a combinatorial game" (PDF). Journal of Combinatorial Theory. Series A. 14 (3): 298–301. doi:10.1016/0097-3165(73)90005-8. MR 0327313.