文章基本信息

标题：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