论文标题
关于使用单一候选选票的多赢家选举的扭曲
On the Distortion of Multi-winner Election Using Single-Candidate Ballots
论文作者
论文摘要
在本文中，我们研究了一般度量空间中多赢家选举的投票机制的失真界限。我们的研究与每个选民在$ m $可能选择中只报告她最喜欢的候选人的情况有关。鉴于候选人的位置未限制在该机制上，因此该机制必须仅根据候选人获得的票数组成$ w- $冠军委员会。我们为真实和非真实机制建立了失真界限。我们的研究突出了$σ$参数的重要性，该参数表示所有候选对之间的最大距离和最小距离之间的比率。我们证明失真为$σ$是线性的。首先，我们证明所有机制的失真大于$ 1+\ frac {w-1} {w+1}（σ-1）$。为了给出上限，我们研究了单个不可转票（SNTV）机制，其失真最多为$ 1+2σ$。其次，我们检索了策略性防护机制的上限。特别是，我们通过检查$ w = 2 $时的随机顺序独裁者机制来推断上界限，该机制的随机顺序独裁者机制小于$ 1+4σ$。
In this paper, we study the distortion bounds for voting mechanisms in multi-winner elections in general metric spaces. Our study pertains to the case in which each voter only reports her favorite candidate amongst $m$ possible choices. Given that candidates' locations are undisclosed to the mechanism, the mechanism has to form a $w-$winner committee based solely on the number of votes received by candidates. We establish distortion bounds for both truthful and non-truthful mechanisms. Our research highlights the significance of the $σ$ parameter, which represents the ratio between maximum and minimum distances among all candidate pairs. We show that the distortion is linear in $σ$. First, we demonstrate that all mechanisms possess a distortion greater than $1+\frac{w-1}{w+1}(σ-1)$. To give an upper bound, we study the Single Non-Transferable Vote (SNTV) mechanism, whose distortion is at most $1+2σ$. Second, we retrieve the upper bounds for strategyproof mechanisms. In particular, we infer an upper bound by examining the Random Sequential Dictator mechanism that achieves a distortion less than $1+4σ$ when $w=2$.
