On β-plurality points in spatial voting games

Let V be a set of n points in R^d, called voters. A point p ∈ R^d is a plurality point for V when the following holds: for every q ∈ 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 ∈ 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 β-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 β, for some constant 0 < β 6 1. We investigate the existence and computation of β-plurality points, and obtain the following results. Define β_d^∗:= sup{β: any finite multiset V in R^d admits a β-plurality point}. We prove that β₂^∗ = ^√3/2, and that 1/^√d 6 β_d^∗ 6 √3/2 for all d > 3. Define β(V ):= sup{β: V admits a β-plurality point}. We present an algorithm that, given a voter set V in R^d, computes an (1 − ε) · β(V ) plurality point in time O(_ε3ⁿ_d²₋₂ · log _εdⁿ₋₁ · log^{2 1}_ε ).