详细内容或原文请订阅后点击阅览
投票的最佳度量失真——书中的证明
在这篇文章中，我们将重新讨论投票理论中的（确定性）度量扭曲猜想，该猜想最近由 Gkatzelis、Halpern 和 Shah [GHS20] 证明，并由 Kempe 和 Kizilkaya [KK22] 优雅地重新证明。该猜想涉及以下问题。假设我们举行一场选举，选民和候选人位于度量空间中，但我们唯一拥有的信息是选民按距离递增顺序对候选人的排名。候选人的成本是他们与选民的总距离。我们能否设计一条投票规则，始终选择成本接近最低可能的候选人？（理想情况下，只比最小值差一个小因素，在文献中称为扭曲。）先验地，这似乎是一项不可能完成的任务。如果不知道实际距离，你怎么可能做到这一点？事实证明，知道距离的相对顺序以及三角不等式就足以得到最多为常数的扭曲。可以实现的最小常数是多少？下面描述的一个简单示例表明，不可能获得比失真 3 更好的结果。想象一下有两位候选人（红点）和两位选民的选举 [...]
来源:理论盘点博客在这篇文章中，我们将重新讨论投票理论中的（确定性）度量扭曲猜想，该猜想最近由 Gkatzelis、Halpern 和 Shah [GHS20] 证明，并由 Kempe 和 Kizilkaya [KK22] 优雅地重新证明。
GHS20 KK22该猜想涉及以下问题。假设我们有一个选举，选民和候选人位于度量空间中，但我们唯一拥有的信息是选民按距离递增顺序对候选人的排名。候选人的成本是他们与选民的总距离。我们能否设计一个投票规则，始终选择成本接近最低可能的候选人？（理想情况下，只比最小值差一个小因素，在文献中称为扭曲。）先验地，这似乎是一项不可能完成的任务。如果不知道实际距离，你怎么可能做到这一点？事实证明，了解距离的相对顺序以及三角不等式足以得到最多为常数的失真。可以实现的最小常数是多少？
成本 失真下面描述的简单示例表明，不可能获得比失真 3 更好的效果。想象一场有两个候选人（红点）和两个对候选人排名相反的选民（蓝点，标有他们的排名）的选举。然后考虑线上度量的两个实现，其中一个选民与他们喜欢的候选人位于同一位置，另一个选民位于两个候选人中间。无论规则选择哪个候选人，在其中一个度量中，另一个候选人的成本只有三分之一。
ABP15 科普兰规则 MW19 Kem20 GHS20 KK22 GHS20定理。假设我们有一个选举，候选人和选民位于一个距离度量为 的度量空间中。在选举中，每个选民按距离的顺序对候选人进行排名（如果 则 ）。然后有一个确定性的投票规则，选择候选人，使得对于任何候选人 ，定理。 证明。 KK22 分数 否决 CR22