Waiter–Client game
Waiter–Client game
A Waiter-Client game (also called: Picker-Chooser game) is a kind of positional-game. Like most positional games, it is described by its set of positions/points/elements (<math>X</math>), and its family of winning-sets (<math>\mathcal{F}</math>- a family of subsets of <math>X</math>). 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. 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.
This leads to the following conjecture by józsef-beck:
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 <math>2^{k-1}</math> . However, currently only the following weaker bounds are known:
- Waiter wins if the number of winning-sets is less than <math>{2^{k-1} \over 8(k+1)}</math> .
- Waiter wins if the number of winning-sets is less than <math>{2^{k-1} \over 3\sqrt{k+1/2}}</math> .