science

Waiter–Client game

Waiter–Client game is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Waiter–Client game rather than just read about it. In short: 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 ( X {\displaystyle X} ), and its family of winning-sets ( F {\displaystyle {\mathcal {F}}} - a family of subsets of X {\displaystyle X} ).

Key takeaways

Waiter–Client game belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Waiter–Client game to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Waiter–Client game from memory before moving on to harder problems.

Reference excerpt

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 ( X {\displaystyle X} ), and its family of winning-sets ( F {\displaystyle {\mathcal {F}}} - a family of subsets of X {\displaystyle 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. 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: If Maker wins the Maker-Breaker game on ( X , F ) {\displaystyle (X,{\mathcal {F}})} when playing second, then Waiter wins the Waiter-Client game on ( X , F ) {\displaystyle (X,{\mathcal {F}})} . Similarly, if Breaker wins the Maker-Breaker game on ( X , F ) {\displaystyle (X,{\mathcal {F}})} when playing second, then Waiter wins the Client-Waiter game on ( X , F ) {\displaystyle (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 {\displaystyle 2^{k-1}} . 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 {\displaystyle 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 8 ( k + 1 ) {\displaystyle {2^{k-1} \over 8(k+1)}} . Waiter wins if the number of winning-sets is less than 2 k − 1 3 k + 1 / 2 {\displaystyle {2^{k-1} \over 3{\sqrt {k+1/2}}}} .

References

Worked examples

Example 1 — a first encounter with Waiter–Client game

Start with the simplest possible case. Write down what Waiter–Client game claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Waiter–Client game before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Waiter–Client game ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Waiter–Client game

In research: Waiter–Client game appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Waiter–Client game in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Waiter–Client game is common in secondary-school and first-year university syllabi. It links to neighbouring topics Positional games, so understanding it makes those chapters shorter.
In everyday life: Look for Waiter–Client game outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Waiter–Client game” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Waiter–Client game in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Waiter–Client game means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Waiter–Client game out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Waiter–Client game in simple terms?

Why does Waiter–Client game matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Waiter–Client game?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Waiter–Client game.