Abstract
In this thesis, we first study two broad questions, based on two different `voting games'. These questions are natural from the perspective of both voting theory and combinatorics. The final chapter concerns a combinatorial question about directed graphs. In the second and final chapters, we also study the complexity of the relevant algorithms.In Chapter 2, we look at a two-player game in Euclidean space. Given a finite set $S$ of voters in $\mathbb{R}^d$, the players choose any point in $\mathbb{R}^d$, one after the other. Each voter votes for the player closest to them, in terms of Euclidean distance. The player with the most votes wins (the first player wins in case of equal votes). We specify the sets $S$ for which each player wins, for all $d$.
In Chapter 3, we look at a variant of the problem above, where the second player has to pick a point at distance $\delta$ from the first player. For $d=2$, we determine the smallest value of $\delta$ (in terms of the diameter of $S$) that guarantees a first player win.
In Chapter 4, we look at a four-player game on the hypercube $Q_n=\{0,1\}^n$. There is a single voter at each vertex, and each player chooses a vertex. Each voter votes for the player closest to them in terms of Hamming distance (the vote is equally divided between multiple players if necessary). We show that such a profile is an equilibrium (no player can increase their score by moving) if and only if it is balanced (in each coordinate, exactly two players have chosen $0$).
In Chapter 5, we determine the maximum number of edges in a directed graph that has the following property: If there is an edge from $u$ to $v$, then there is no other path from $u$ to $v$.
| Date of Award | 20 Jan 2026 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | David C Ellis (Supervisor) |
Cite this
- Standard