Back to search

University of Birmingham

Waiter–Client and Client–Waiter games

Abstract

dc:description.abstract

In this thesis, we consider two types of positional games; \(Waiter\)-\(Client\) and \(Client\)-\(Waiter\) games. Each round in a biased (\(a\):\(b\)) game begins with Waiter offering a+b free elements of the board to Client. Client claims \(a\) elements among these and the remaining \(b\) elements are claimed by Waiter. Waiter wins in a Waiter-Client game if he can force Client to fully claim a \(winning\) \(set\), otherwise Client wins. In a Client-Waiter game, Client wins if he can claim a winning set himself, else Waiter wins. We estimate the \(threshold\) \(bias\) of four different (\(1\):\(q\)) Waiter-Client and Client-Waiter games. This is the unique value of Waiter's bias \(q\) at which the player with a winning strategy changes. We find its asymptotic value for both versions of the complete-minor and non-planarity games and give bounds for both versions of the non-\(r\)-colourability and \(k\)-SAT games. Our results show that these games exhibit a heuristic called the \(probabilistic\) \(intuition\). We also find sharp probability thresholds for the appearance of a graph in the random graph \(G\)(\(n\),\(p\)) on which Waiter and Client win the (\(1\):\(q\)) Waiter-Client and Client-Waiter Hamiltonicity games respectively.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tan, Wei En

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Tan, Wei En. Waiter–Client and Client–Waiter games. d_ph thesis, University of Birmingham, 2017.