文章基本信息
- 标题：On β-Plurality Points in Spatial Voting Games
- 本地全文：下载
- 作者：Boris Aronov ; Mark de Berg ; Joachim Gudmundsson 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：164
- 页码：7:1-7:15
- DOI：10.4230/LIPIcs.SoCG.2020.7
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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 β^*â,, = â^S3/2, and that 1/â^Sd ⩽ β^*_d ⩽ â^S3/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/ε)).
- 关键词：Computational geometry; Spatial voting theory; Plurality point; Computational social choice
