解决最优度量失真猜想

Apr, 2020

Resolving the Optimal Metric Distortion Conjecture

Vasilis Gkatzelis, Daniel Halpern, Nisarg Shah

TL;DR研究度量扭曲问题：有两个点集 V 和 C，它们在相同的度量空间中，我们的目标是选择 C 中一点，其到 V 点的总距离尽可能小。我们提出了使用排名作为输入的算法，并提供了它们的扭曲界限。

Abstract

We study the following metric distortion problem: there are two finite sets of points, $V$ and $C$, that lie in the same metric space, and our goal is to choose a point in $C$ whose total distance from the points in $V$ is as small as possible. However, rather than having access to the

metric distortion problem voting theory distortion bounds ranking-matching lemma randomized algorithm

发现论文，激发创造

突破度量投票扭曲壁垒

研究了社会选择中度量失真问题，给出了一种新的投票规则，通过随机化最大允许值与新规则可实现失真小于 2.753，其为计算社会选择中重要而具有挑战性的问题。

Jun, 2023

度量投票中的通信、失真和随机性

研究了基于歪曲的社会选择规则和基于度量空间的投票机制，在确定性社会选择规则和随机化社会选择规则中探讨畸变和沟通量之间的比较，并构建了一种新的随机化社会选择规则，达到了期望畸变的下界。

Nov, 2019

社会选择规则的度量失真：下界与公平性质

本文研究了社会选择规则在利益最大化失真框架下的表现，并探讨了 Ranked Pairs 及 Copeland rule 的最坏失真情况，以及随机化对于比赛的影响。另外，我们证明了 Copeland 和 Randomized Dictatorship 具有较低的公平性比率。

Dec, 2016

投票者激情意识极大地提高了度量社会选择的失真度

该研究开发了一种新的投票机制，旨在选择能够最大程度降低社会成本（即选民与候选人之间的总距离）的候选人，并量化了关于候选人失真度和投票者偏好力量信息之间的权衡。

Jun, 2019

度量扭曲与社会选择规则公平性的关系

本篇文章是通过一种效用歪曲的框架来评估社会选择（投票）规则，其中利用代理人提交的完整排名来生成社会成本，从而探讨选举规则的失真度和公平比率等概念。其中提出的 Copeland rule 实现了至多 5 的失真度和公平比率的两个指标，并将单赢家规则的失真度和多赢家规则联系起来，基于此引出 Recursive Copeland 规则在选择一组备选方案时，实现了 5 的失真度和 7 以下的公平比率。

Oct, 2018

最佳失真双世界

本文研究了基于代理人的顺序偏好设计投票规则的问题，并使用 “变形度量” 来衡量投票规则的性能，旨在最大化所有代理人的快乐度，文中研究了两个不同的投票变形世界：功利变形和度量变形，并证明了可以通过设计新的投票规则同时达到两种变形下的最优性能。

May, 2023

多数否决：一种实现最优度量扭曲的简单投票规则

提出了一种名为 Plurality Veto 的简单的投票规则，它只需进行两次查询，就可以实现 “失真度” 的最优解，并进一步将其推广为更广泛的随机化投票规则。

Jun, 2022

度量偏好下的随机社会选择函数

本文讨论了基于代价度量的随机社会选择机制的质量，在代理人的度量代价未知的情况下，从多个备选方案选择最优备选方案

Dec, 2015

关于度量的 Ramsey 型现象

研究关于有限度量空间的非线性模拟，探索其与希尔伯特空间的扭曲嵌入子空间的基数，并给出了关于嵌入和扭曲的任意精度下限和上限。

Jun, 2004

度量空间中的比例代表与低失真委员会选取

我们引入了一种新的定义，即在度量空间中，对于一个要表示的集合 V（如文件或选民）和一组可能的代表 C，我们的标准要求对于 V 的任何包含 theta 分数的子集 S，S 到其在 R 中最佳的 theta*k 个点的平均距离与其到 C 中所有点的最佳 theta*k 个点的平均距离相比，不超过一个因子 gamma。

Dec, 2023