On beta-Plurality Points in Spatial Voting Games

Abstract

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 $β^*_d := \sup \{ β: \text{any finite multiset $V$in$\mathbb{R}^d$admitsa$β$-plurality point} \}$. We prove that ${\beta }_2^{\ast }=\sqrt{3}/2$, and that $1/\sqrt{d}\le {\beta }_d^{\ast }\le \sqrt{3}/2$ for all $d\ge 3$. * Define $β(p, V) := \sup \{ β: \text{$p$isa$β$-pluralitypointfor$V$}\}$. Given a voter set $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/\sqrt{d}$ in $O(n)$ time. * Define $β(V) := \sup \{ β: \text{$V$admitsa$β$-plurality point}\}$. We present an algorithm that, given a voter set $V$ in ${\mathbb{R}}^d$, computes an $(1-\epsilon )\cdot \beta (V)$ plurality point in time $O(\frac{n^2}{{\epsilon }^{3d-2}}\cdot \log \frac{n}{{\epsilon }^{d-1}}\cdot {\log }^2\frac{1}{\epsilon })$.

21 pages, 10 figures, SoCG'20