Waiter-Client and Client-Waiter colourability games on a -uniform hypergraph and the -SAT game
Waiter-Client and Client-Waiter games are two-player, perfect information games, with no chance moves, played on a finite set (board) with special subsets known as the winning sets. Each round of the biased game begins with Waiter offering previously unclaimed elements of the board to Client, who claims one. The elements remaining are then claimed by Waiter. If Client fully claims a winning set by the time all board elements have been offered, he wins in the Client-Waiter game and loses in the Waiter-Client game. We give an estimate for the threshold bias of the Waiter-Client and Client-Waiter versions of two different games: the non-2-colourability game, played on the complete -uniform hypergraph, and the -SAT game. In particular, we show that the unique value of at which the winner of the Client-Waiter version of the non-2-colourability game changes is and, for the Waiter-Client version, the corresponding value of is . Additionally, we show that the threshold bias for the Waiter-Client and Client-Waiter versions of the -SAT game is up to a factor that is exponential and polynomial in respectively. This shows that these games exhibit the "probabilistic intuition".