On beta-Plurality Points in Spatial Voting Games

Boris Aronov, Mark T. de Berg, Joachim Gudmundsson, Michael Horton

Research output: Contribution to journalArticleAcademic

113 Downloads (Pure)

Abstract

Let V be a set of n points in Rd, called voters. A point p∈Rd is a plurality point for V when the following holds: for every q∈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 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<β≤1. We investigate the existence and computation of β-plurality points, and obtain the following results. * Define β∗d:=sup{β:any finite multiset V in Rd admits a β-plurality point}. We prove that β∗2=3–√/2, and that 1/d−−√≤β∗d≤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 Rd, computes an (1−ε)⋅β(V) plurality point in time O(n2ε3d−2⋅lognεd−1⋅log21ε).
Original languageEnglish
Article number2003.07513
Number of pages18
JournalarXiv
Volume2020
DOIs
Publication statusPublished - 17 Mar 2020

Keywords

  • Computer Science
  • Computational Geometry

Fingerprint

Dive into the research topics of 'On beta-Plurality Points in Spatial Voting Games'. Together they form a unique fingerprint.

Cite this