论文标题
在空间投票游戏中的Beta-Plurality点上
On beta-Plurality Points in Spatial Voting Games
论文作者
论文摘要
令$ v $为$ \ m athbb {r}^d $中的$ n $点，称为选民。 \ Mathbb {r}^d $ in Point $ p \是$ v $的复数点：对于以下$ q \ in \ mathbb {r}^d $，每一个接近$ q $的选民人数都比接近$ q $ p $ p $ $ q $。因此，在投票中，每张$ v \ in V $投票在最近的提案中（以及提案相同距离的选民），提案$ p $不会因任何替代提案$ q $而损失。对于大多数选民而言，不存在多数点。因此，我们介绍了$β$ - 普遍点的概念，该概念与常规复数点相似，除了每个选民到$ p $（但不是$ q $）的距离由因子$β$缩放，对于某种常数$ 0 <β\ leq 1 $。我们研究了$β$ - 质量点的存在和计算，并获得以下内容。 *定义$β^* _ d：= \ sup \ {β：\ text {$ \ mathbb {r}^d $ in $ \ m mathbb {r}^d $允许$β$ -plurality point} \} $。我们证明$β^*_ 2 = \ sqrt {3}/2 $，以及$ 1/\ sqrt {d} \ leqβ^*_ d \ leq \ leq \ leq \ sqrt {3} {3}/2 $ for All $ d \ geq 3 $。 *定义$β（p，v）：= \ sup \ {β：\ text {$ p $是$β$ - plurality点的$ v $} \} $。给定一个选民集$ v \ in \ mathbb {r}^2 $，我们提供了一种以$ o（n \ log n）$时间运行的算法，并计算一个点$ p $，使$β（p，v）\ geqβ^*_ 2 $ 2 $。此外，对于$ d \ geq 2 $，我们可以用$β（p，v）\ geq 1/\ sqrt {d} $计算点$ p $，in $ o（n）$ time。 *定义$β（v）：= \ sup \ {β：\ text {$ v $允许$β$ -plurality point} \} $。我们提出了一种算法，给定一个选民设置$ \ \ m \ m i \ mathbb {r}^d $，计算一个$（1- \ varepsilon）\ cdotβ（v）$ pyprality in Time $ o（\ frac {n^2} {N^2} {\ varepsilon^{ \ frac {n} {\ varepsilon^{d-1}}} \ cdot \ log^2 \ frac {1} {\ varepsilon}）$。
Let $V$ be a set of $n$ points in $\mathbb{R}^d$, called voters. A point $p\in \mathbb{R}^d$ is a plurality point for $V$ when the following holds: for every $q\in\mathbb{R}^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\in 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<β\leq 1$. We investigate the existence and computation of $β$-plurality points, and obtain the following. * Define $β^*_d := \sup \{ β: \text{any finite multiset $V$ in $\mathbb{R}^d$ admits a $β$-plurality point} \}$. We prove that $β^*_2 = \sqrt{3}/2$, and that $1/\sqrt{d} \leq β^*_d \leq \sqrt{3}/2$ for all $d\geq 3$. * Define $β(p, V) := \sup \{ β: \text{$p$ is a $β$-plurality point for $V$}\}$. Given a voter set $V \in \mathbb{R}^2$, we provide an algorithm that runs in $O(n \log n)$ time and computes a point $p$ such that $β(p, V) \geq β^*_2$. Moreover, for $d\geq 2$ we can compute a point $p$ with $β(p,V) \geq 1/\sqrt{d}$ in $O(n)$ time. * Define $β(V) := \sup \{ β: \text{$V$ admits a $β$-plurality point}\}$. We present an algorithm that, given a voter set $V$ in $\mathbb{R}^d$, computes an $(1-\varepsilon)\cdot β(V)$ plurality point in time $O(\frac{n^2}{\varepsilon^{3d-2}} \cdot \log \frac{n}{\varepsilon^{d-1}} \cdot \log^2 \frac {1}{\varepsilon})$.
