TY - JOUR

T1 - On β-Plurality Points in Spatial Voting Games

AU - Aronov, Boris

AU - De Berg, Mark

AU - Gudmundsson, Joachim

AU - Horton, Michael

N1 - Publisher Copyright:
© 2021 ACM.

PY - 2021/8

Y1 - 2021/8

N2 - 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).

AB - 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).

KW - Computational geometry

KW - computational social choice

KW - plurality point

KW - spatial voting theory

UR - http://www.scopus.com/inward/record.url?scp=85112026071&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85112026071&partnerID=8YFLogxK

U2 - 10.1145/3459097

DO - 10.1145/3459097

M3 - Article

AN - SCOPUS:85112026071

SN - 1549-6325

VL - 17

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 3

M1 - 24

ER -