On β-plurality points in spatial voting games

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 < β 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(ε3nd22 · log εdn1 · log2 1ε ).

    Original languageEnglish (US)
    Title of host publication36th International Symposium on Computational Geometry, SoCG 2020
    EditorsSergio Cabello, Danny Z. Chen
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959771436
    DOIs
    StatePublished - Jun 1 2020
    Event36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland
    Duration: Jun 23 2020Jun 26 2020

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    Volume164
    ISSN (Print)1868-8969

    Conference

    Conference36th International Symposium on Computational Geometry, SoCG 2020
    CountrySwitzerland
    CityZurich
    Period6/23/206/26/20

    Keywords

    • Computational geometry
    • Computational social choice
    • Plurality point
    • Spatial voting theory

    ASJC Scopus subject areas

    • Software

    Fingerprint Dive into the research topics of 'On β-plurality points in spatial voting games'. Together they form a unique fingerprint.

    Cite this