论文标题
与常数$β$的空间投票游戏中的多数
Plurality in Spatial Voting Games with constant $β$
论文作者
论文摘要
考虑一套$ v $的选民，以度量空间$（x，d）$中的多键表示。选民必须做出决定 - $ x $的一点。 x $中的选择$ p \在x $中称为$β$ - plurality点，如果对于任何其他选择$ q \ in x $中的$ q \，则认为$ | \ {v \ in V \ midβ\ cdot d（p，v）\ le d（q，q，q，q，v）换句话说，当额外的$β$以$ p $为$β$时，至少有一半的选民``'''''''feave''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''对于$β= 1 $，这相当于很少存在的Condorcet获胜者。 Aronov，de Berg，Gudmundsson和Horton [TALG 2021]提出了$β$ - 普遍性的概念，以此作为Condorcet标准的放松。 令$β^*_ {（x，d）} = \ sup \ {β\ mid \ mbox {$ x $ in $ x $ in $ x $ in $β$ - plurality point} \} $ in $ x $中的每个有限的多秒$ v $。参数$β^*$确定要达到稳定决定所需的放松量。 Aronov等。 showed that for the Euclidean plane $β^*_{(\mathbb{R}^2,\|\cdot\|_2)}=\frac{\sqrt{3}}{2}$, and more generally, for $d$-dimensional Euclidean space, $ \ frac {1} {\ sqrt {d}} \leβ^*_ {（\ Mathbb {r}^d，\ | \ | \ cdot \ | _2）} \ le \ le \ frac {\ frac {\ sqrt {3}}} {2}} {2} {2} $。在本文中，我们表明$ 0.557 \leβ^*_ {（\ Mathbb {r}^d，\ | \ cdot \ | _2）} $对于任何维度$ d $此外，我们证明，对于每个度量空间$（x，d）$，它认为$ \ sqrt {2} -1 \leβ^*_ {（x，d，d）} $，并证明存在$β^*_ {（x，x，d）} \ le \ frac12 $。
Consider a set $V$ of voters, represented by a multiset in a metric space $(X,d)$. The voters have to reach a decision -- a point in $X$. A choice $p\in X$ is called a $β$-plurality point for $V$, if for any other choice $q\in X$ it holds that $|\{v\in V\mid β\cdot d(p,v)\le d(q,v)\}|\ge\frac{|V|}{2}$. In other words, at least half of the voters ``prefer'' $p$ over $q$, when an extra factor of $β$ is taken in favor of $p$. For $β=1$, this is equivalent to Condorcet winner, which rarely exists. The concept of $β$-plurality was suggested by Aronov, de Berg, Gudmundsson, and Horton [TALG 2021] as a relaxation of the Condorcet criterion. Let $β^*_{(X,d)}=\sup\{β\mid \mbox{every finite multiset $V$ in $X$ admits a $β$-plurality point}\}$. The parameter $β^*$ determines the amount of relaxation required in order to reach a stable decision. Aronov et al. showed that for the Euclidean plane $β^*_{(\mathbb{R}^2,\|\cdot\|_2)}=\frac{\sqrt{3}}{2}$, and more generally, for $d$-dimensional Euclidean space, $\frac{1}{\sqrt{d}}\le β^*_{(\mathbb{R}^d,\|\cdot\|_2)}\le\frac{\sqrt{3}}{2}$. In this paper, we show that $0.557\le β^*_{(\mathbb{R}^d,\|\cdot\|_2)}$ for any dimension $d$ (notice that $\frac{1}{\sqrt{d}}<0.557$ for any $d\ge 4$). In addition, we prove that for every metric space $(X,d)$ it holds that $\sqrt{2}-1\leβ^*_{(X,d)}$, and show that there exists a metric space for which $β^*_{(X,d)}\le \frac12$.
