论文标题
多数否决：实现最佳度量失真的简单投票规则
Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion
论文作者
论文摘要
该度量扭曲框架认为，n个选民和M候选人共同嵌入到公制空间中，因此选民对候选人的候选人更加接近。投票规则的目的是仅鉴于排名，而不是实际距离，挑选了与选民总距离最小距离的候选人。结果，在最坏的情况下，每个确定性规则都选择了一个候选人，其总距离至少比最佳距离大三倍，即至少有3倍的变形。最近的突破结果表明，实现3个结合是可能的；但是，证明是非构造性的，投票规则本身是一个复杂的详尽搜索。 我们的主要结果是一个非常简单的投票规则，称为多数否决权，它实现了3个最佳失真。每个候选人的得分都等于他的第一名投票数量。然后，这些分数通过N-ROND否决过程逐渐降低，在该过程中，当候选人得分达到零时，候选人会退出。一个接一个地，选民在常设候选人中降低了他们最不可能的选择，最后一名常设候选人赢得了胜利。我们给出一个单段证明，该投票规则实现了失真3。该规则也非常实用，它仅对每个选民进行两个疑问，因此它的沟通开销较低。 我们还通过以下方式将多元化否决权否决为一类随机投票规则：复数否决权仅用于K <n回合；然后，选择候选人的概率与他的剩余分数成正比。该一般规则在随机独裁统治（对于K = 0）和多数否决（对于K = N-1）之间，而K控制输出的方差。我们表明，对于所有K，该规则最多都有3个。
The metric distortion framework posits that n voters and m candidates are jointly embedded in a metric space such that voters rank candidates that are closer to them higher. A voting rule's purpose is to pick a candidate with minimum total distance to the voters, given only the rankings, but not the actual distances. As a result, in the worst case, each deterministic rule picks a candidate whose total distance is at least three times larger than that of an optimal one, i.e., has distortion at least 3. A recent breakthrough result showed that achieving this bound of 3 is possible; however, the proof is non-constructive, and the voting rule itself is a complicated exhaustive search. Our main result is an extremely simple voting rule, called Plurality Veto, which achieves the same optimal distortion of 3. Each candidate starts with a score equal to his number of first-place votes. These scores are then gradually decreased via an n-round veto process in which a candidate drops out when his score reaches zero. One after the other, voters decrement the score of their bottom choice among the standing candidates, and the last standing candidate wins. We give a one-paragraph proof that this voting rule achieves distortion 3. This rule is also immensely practical, and it only makes two queries to each voter, so it has low communication overhead. We also generalize Plurality Veto into a class of randomized voting rules in the following way: Plurality veto is run only for k < n rounds; then, a candidate is chosen with probability proportional to his residual score. This general rule interpolates between Random Dictatorship (for k=0) and Plurality Veto (for k=n-1), and k controls the variance of the output. We show that for all k, this rule has distortion at most 3.
