On beta-Plurality Points in Spatial Voting Games

Let $V$ be a set of $n$ points in ${\mathbb{R}}^d$, called voters. A point $p\in {\mathbb{R}}^d$ is a plurality point for $V$ when the following holds: for every $q\in {\mathbb{R}}^d$ the number of voters closer to $p$ than to $q$ is at least the number of voters closer to $q$ than to $p$. Thus, in a vote where each $v\in V$ votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal $p$ will not lose against any alternative proposal $q$. For most voter sets a plurality point does not exist. We therefore introduce the concept of $\beta$-plurality points, which are defined similarly to regular plurality points except that the distance of each voter to $p$ (but not to $q$) is scaled by a factor $\beta$, for some constant $0<\beta \le 1$. We investigate the existence and computation of $\beta$-plurality points, and obtain the following.

• Define \beta^*_d := \sup \{ \beta : \text{any finite multisetV$in$$\mathbb{R}$^d$admitsa$\beta-plurality point} \}. We prove that $\beta^_2 = \sqrt{3}/2$,andthat$1/\sqrt{d} \leq \beta^_d \leq \sqrt{3}/2$forall$d\geq 3$.
• Define \beta(p, V) := \sup \{ \beta : \text{p$isa$\beta$-plurality point for $V$}}$\mathrm{.}Givenavoterset$V \in $\mathbb{R}$^2$, we provide an algorithm that runs in $O(n\log n)$ time and computes a point $p$ such that $\beta (p,V)\ge {\beta }_2^{\ast }$. Moreover, for $d\ge 2$ we can compute a point $p$ with $\beta (p,V)\ge 1\mathrm{/}\sqrt{d}$ in $O(n)$ time.
• Define \beta(V) := \sup \{ \beta : \text{V$admitsa$\beta$-plurality point}}$\mathrm{.}Wepresentanalgorithmthat,givenavoterset$V$in$$\mathbb{R}$^d$,computesan$(1-\varepsilon)\cdot \beta(V)$ plurality point in time $O(\frac{n^2}{\varepsilon^{3d-2}} \cdot \log \frac{n}{\varepsilon^{d-1}} \cdot \log^2 \frac {1}{\varepsilon})$.