Optimal Metric Distortion for Voting — A Proof from the Book
在这篇文章中，我们将重新讨论投票理论中的（确定性）度量扭曲猜想，该猜想最近由 Gkatzelis、Halpern 和 Shah [GHS20] 证明，并由 Kempe 和 Kizilkaya [KK22] 优雅地重新证明。该猜想涉及以下问题。假设我们举行一场选举，选民和候选人位于度量空间中，但我们唯一拥有的信息是选民按距离递增顺序对候选人的排名。候选人的成本是他们与选民的总距离。我们能否设计一条投票规则，始终选择成本接近最低可能的候选人？（理想情况下，只比最小值差一个小因素，在文献中称为扭曲。）先验地，这似乎是一项不可能完成的任务。如果不知道实际距离，你怎么可能做到这一点？事实证明，知道距离的
