TY - GEN

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: Partially supported by NSF grant CCF-15-40656 and by grant 2014/170 from the US-Israel Binational Science Foundation. Mark de Berg: Supported by the Netherlands' Organisation for Scientific Research (NWO) under project no. 024.002.003. Joachim Gudmundsson: Supported under the Australian Research Council Discovery Projects funding scheme (project numbers DP150101134 and DP180102870). Michael Horton: Part of the work performed on this paper was done while visiting NYU, supported by NSF grant CCF 12-18791. The authors would like to thank Sampson Wong for improving an earlier version of Lemma 2.6.
Funding Information:
Funding Boris Aronov: Partially supported by NSF grant CCF-15-40656 and by grant 2014/170 from the US-Israel Binational Science Foundation. Mark de Berg: Supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 024.002.003. Joachim Gudmundsson: Supported under the Australian Research Council Discovery Projects funding scheme (project numbers DP150101134 and DP180102870). Michael Horton: Part of the work performed on this paper was done while visiting NYU, supported by NSF grant CCF 12-18791.

PY - 2020/6/1

Y1 - 2020/6/1

N2 - 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 < β 6 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 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 Rd, computes an (1 − ε) · β(V ) plurality point in time O(ε3nd2−2 · log εdn−1 · log2 1ε ).

AB - 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 < β 6 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 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 Rd, computes an (1 − ε) · β(V ) plurality point in time O(ε3nd2−2 · log εdn−1 · log2 1ε ).

KW - Computational geometry

KW - Computational social choice

KW - Plurality point

KW - Spatial voting theory

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

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

U2 - 10.4230/LIPIcs.SoCG.2020.7

DO - 10.4230/LIPIcs.SoCG.2020.7

M3 - Conference contribution

AN - SCOPUS:85086499474

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 36th International Symposium on Computational Geometry, SoCG 2020

A2 - Cabello, Sergio

A2 - Chen, Danny Z.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 36th International Symposium on Computational Geometry, SoCG 2020

Y2 - 23 June 2020 through 26 June 2020

ER -