Definition
A Waiter–Client game is a two‑player positional game in combinatorial game theory. The game is played on a finite set $X$ (the board) together with a family $\mathcal{F}\subseteq 2^{X}$ of winning sets. In each round, one player, called Waiter, offers a prescribed number $q$ of previously unclaimed elements of $X$. The other player, called Client, selects one of the offered elements; the remaining $q-1$ elements are taken by Waiter. The game proceeds until all elements of $X$ are claimed. The outcome is determined by which player’s claimed set contains a winning set from $\mathcal{F}$: typically, Client wins if his claimed elements contain a member of $\mathcal{F}$; otherwise Waiter wins.
Overview
The Waiter–Client game belongs to the class of biased positional games, where a bias parameter $q$ (often written as a $1!:! (q-1)$ bias) controls how many elements are offered versus how many are taken each round. The game is impartial with respect to the structure of the board but asymmetric in the roles of the players: Waiter controls the presentation of options, while Client exercises the final choice.
The Waiter–Client framework mirrors the more widely known Maker–Breaker and Avoider–Enforcer games, but the strategic considerations differ because Waiter can influence the set of choices available to Client each turn. Several results parallel those for Maker–Breaker games, such as threshold bias theorems that identify for a given family $\mathcal{F}$ the values of $q$ for which Client (the “Maker” analogue) has a winning strategy. The game has been studied on various boards, including complete graphs, hypergraphs, and random structures.
Etymology / Origin
The terminology “Waiter–Client” was introduced in the early 2000s in the combinatorial game theory literature to denote this particular asymmetric offering/selection mechanism. The concept appears in research articles by J. Beck (e.g., Positional Games, 2008) and subsequent works by D. Hefetz, M. Krivelevich, and others, who formalised the model and investigated its properties. The names reflect the real‑world analogy of a waiter presenting a menu of dishes (the offered elements) from which a client selects one.
Characteristics
-
Board and Winning Sets: A finite set $X$ together with a family $\mathcal{F}\subseteq 2^{X}$. Typical examples include the set of edges of a complete graph with $\mathcal{F}$ consisting of all edges forming a Hamiltonian cycle, a spanning tree, or a complete subgraph $K_{k}$.
-
Bias Parameter: In a $(1:q)$ Waiter–Client game, Waiter offers $q+1$ unclaimed elements each round; Client takes one, Waiter receives the remaining $q$. Variants allow asymmetric biases such as $(a:b)$ where Waiter offers $a+b$ elements and the split is $a$ to Client, $b$ to Waiter.
-
Winning Condition: Usually defined so that Client wins if his claimed set contains some $F\in\mathcal{F}$; otherwise Waiter wins. Alternative conventions swap the roles, but the literature generally adopts the above.
-
Strategy and Thresholds: Results often establish a threshold bias $q_{\mathrm{th}}$ such that for $q < q_{\mathrm{th}}$ Client has a winning strategy, while for $q > q_{\mathrm{th}}$ Waiter can force a win. Techniques involve potential functions, random strategies, and connections to Maker–Breaker games via the bias monotonicity principle.
-
Relation to Other Games: The Waiter–Client game can be viewed as a biased version of the Chooser–Picker game, and it is dual to the Client–Waiter variant where the roles of offering and choosing are interchanged.
Related Topics
- Maker–Breaker game – another biased positional game where Maker claims a single element each round and Breaker claims the rest.
- Avoider–Enforcer game – a positional game focusing on avoiding certain configurations.
- Positional games – the broader class of games played on a board with a predefined family of winning sets.
- Combinatorial game theory – the mathematical framework encompassing impartial and partizan games.
- Bias and threshold functions – central concepts in the analysis of positional games.
- Random graph theory – often provides the underlying board for probabilistic versions of Waiter–Client games.