2026-07-22T02:09:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12165 2024-03-06T10:49:36Z ddc:004 open_access

On β-Plurality Points in Spatial Voting Games Aronov, Boris de Berg, Mark Gudmundsson, Joachim Horton, Michael Computational geometry Spatial voting theory Plurality point Computational social choice Let V be a set of n points in ℝ^d, called voters. A point p ∈ ℝ^d is a plurality point for V when the following holds: for every q ∈ ℝ^d 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 ℝ^d admits a β-plurality point}. We prove that β^*₂ = √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 {ℝ}^d, computes an (1-ε)⋅ β(V) plurality point in time O(n²/ε^(3d-2) ⋅ log(n/ε^(d-1)) ⋅ log²(1/ε)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boris Aronov and Mark de Berg and Joachim Gudmundsson and Michael Horton 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.7 urn:nbn:de:0030-drops-121651 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.7 eng https://creativecommons.org/licenses/by/3.0/legalcode