On β-Plurality Points in Spatial Voting Games

Let V be a set of n points in mathcal Rd, called voters. A point p mathcal Rd is a plurality point for V when the following holds: For every q mathcal Rd, 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 vV 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< β 1/2 1. We investigate the existence and computation of β-plurality points and obtain the following results. •Define β∗d := {β : any finite multiset V in mathcal Rd admits a β-plurality point. We prove that β∗d = s3/2, and that 1/s d 1/2 β∗d 1/2 s 3/2 for all d3/4 3. •Define β (p, V) := sup {β : p is a β -plurality point for V}. Given a voter set V in mathcal R2, we provide an algorithm that runs in O(n log n) time and computes a point p such that β (p, V) 3/4 β∗b. Moreover, for d3/4 2, we can compute a point p with β (p,V) 3/4 1/s d in O(n) time. •Define β (V) := sup { β : V admits a β -plurality point}. We present an algorithm that, given a voter set V in mathcal Rd, computes an ((1-I)A β (V))-plurality point in time On2I 3d-2 A log n I d-1 A log 2 1I).