Waiter–Client game


A Waiter-Client game is a kind of positional game. Like most positional games, it is described by its set of positions/points/elements, and its family of winning-sets. 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.
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 and ). 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: If Maker wins the Maker-Breaker game on when playing second, then Waiter wins the Waiter-Client game on. Similarly, if Breaker wins the Maker-Breaker game on when playing second, then Waiter wins the Client-Waiter game on.

Special cases

k-uniform hypergraphs

Suppose the winning-sets are all of size k. In a Maker-Breaker game, the Erdos-Selfridge theorem implies that Breaker wins if the number of winning-sets is less than.
By the above conjecture, we would expect the same to hold in the corresponding Client-Waiter game - Waiter "should" win whenever the number of winning-sets is less than . However, currently only the following weaker bounds are known:
  • Waiter wins if the number of winning-sets is less than .
  • Waiter wins if the number of winning-sets is less than .