TY - JOUR

T1 - On β-Plurality Points in Spatial Voting Games

AU - Aronov, Boris

AU - De Berg, Mark

AU - Gudmundsson, Joachim

AU - Horton, Michael

N1 - Funding Information:
Boris Aronov was partially supported by NSF Grants No. CCF-15-40656 and No. CCF-12-18791, and by Grant No. 2014/170 from the US-Israel Binational Science Foundation. Mark de Berg was supported by the Dutch Research Council (NWO) under project networks (Grant No. 024.002.003). Joachim Gudmundsson was supported under the Australian Research Council Discovery Projects funding scheme (Projects No. DP150101134 and No. DP180102870). Part of the work performed by Michael Horton was done while he was visiting NYU and was supported by NSF Grant No. CCF-12-18791. Authors’ addresses: B. Aronov, Department of Computer Science & Engineering, Tandon School of Engineering, New York University, 370 Jay Street, Brooklyn, New York 11201, USA; email: boris.aronov@nyu.edu; M. de Berg, Department of Mathematics and Computer Science, PO Box 513, 5600 MB Eindhoven, the Netherlands; email: m.t.d.berg@tue.nl; J. Gud-mundsson and M. Horton, School of Computer Science, University of Sydney, Building J12, 1 Cleveland Street, Darlington NSW 2008, Australia; emails: joachim.gudmundsson@sydney.edu.au, mhor9676@alumni.sydney.edu.au. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2021 Association for Computing Machinery. 1549-6325/2021/07-ART24 $15.00 https://doi.org/10.1145/3459097
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

VL - 17

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 3

M1 - 24

ER -