View source for Waiter–Client game

A '''Waiter-Client game'''<ref name=":1">{{Cite journal|last1=Hefetz|first1=Dan|last2=Krivelevich|first2=Michael|last3=Tan|first3=Wei En|date=2017|title=Waiter–Client and Client–Waiter Hamiltonicity games on random graphs|journal=European Journal of Combinatorics|volume=63|pages=26–43|doi=10.1016/j.ejc.2017.02.002|issn=0195-6698|arxiv=1509.05356|s2cid=11084208 }}</ref> (also called:<ref name=":0">{{Cite journal|last=Beck|first=József|date=2002-04-01|title=Positional Games and the Second Moment Method|journal=Combinatorica|language=en|volume=22|issue=2|pages=169–216|doi=10.1007/s004930200009|s2cid=7005199 |issn=0209-9683}}</ref> '''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 sets|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''.<ref>{{Cite journal|last=Beck|first=József|date=2005|title=Positional Games|url=https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/positional-games/76003E3E59B9C73C5BF06FBA8840E1A6|journal=Combinatorics, Probability and Computing|language=en|volume=14|issue=5–6|pages=649–696|doi=10.1017/S0963548305007078|s2cid=27877713 |issn=1469-2163}}</ref> 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 (2''i'',0) and (2''i'',1)). Moreover, even when the board is finite, Waiter always wins as Breaker when ''k'' >= 8. <ref name=":2">{{Cite journal|last1=Csernenszky|first1=András|last2=Mándity|first2=C. Ivett|last3=Pluhár|first3=András|date=2009|title=On Chooser–Picker positional games|journal=Discrete Mathematics|volume=309|issue=16|pages=5141–5146|doi=10.1016/j.disc.2009.03.051|issn=0012-365X|doi-access=free}}</ref>  

This leads to the following conjecture by [[József Beck]]:<ref name=":0" /> If Maker wins the Maker-Breaker game on <math>(X,\mathcal{F})</math> when playing second, then Waiter wins the Waiter-Client game on <math>(X,\mathcal{F})</math>. Similarly, if Breaker wins the Maker-Breaker game on <math>(X,\mathcal{F})</math> when playing second, then Waiter wins the Client-Waiter game on <math>(X,\mathcal{F})</math>.

== 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 <math>2^{k-1}</math>. <ref name="es">{{cite journal|last1=Erdős|first1=P.|last2=Selfridge|first2=J. L.|author2-link=John Selfridge|year=1973|title=On a combinatorial game|url=https://www.renyi.hu/~p_erdos/1973-10.pdf|journal=[[Journal of Combinatorial Theory]]|series=Series A|volume=14|issue=3|pages=298–301|doi=10.1016/0097-3165(73)90005-8|mr=0327313|author1-link=Paul Erdős|doi-access=free}}</ref>

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> .<ref name=":1" />
* Waiter wins if the number of winning-sets is less than <math>{2^{k-1} \over 3\sqrt{k+1/2}}</math> .<ref name=":2" /> 

== References ==
{{Reflist}}
{{DEFAULTSORT:Waiter-Client game}}
[[Category:Positional games]]