摘要翻译：
基于失真的分析已经成为比较投票机制的一个富有成效的框架。m个投票者和n个候选人共同嵌入到一个（未知）度量空间中，投票者通过与自己的距离不递减来提交候选人的排名。基于提交的排名，社会选择规则选择一个获胜的候选人；获胜者的质量是与选民之间（未知的）距离的总和。规则的选择通常是次优的，它所选择的候选成本与最优候选成本之间的最坏情况之比称为规则的失真。已有研究表明，每个确定性规则的失真至少为3,而Copeland规则及其相关规则保证最坏情况下的失真最多为5；最近的一个结果给出了一个失真$2+\sqrt{5}\大约4.236$的规则。我们提出了一个基于LP对偶和对偶的流解释的框架，为证明社会选择规则扭曲的上界提供了一个更简单、更统一的方法。我们用三个例子说明了这种方法的效用。首先，我们给出了广义弱偏好图中具有从优胜者到最优者的短路径的社会选择规则的Copeland失真上界5的强推广的一个相当简单的证明。此结果的一个特例是恢复最近的$2+\SQRT{5}$保证。其次，利用这个广义界，我们证明了排序对和Schulze规则存在畸变$\theta(\sqrt(n))$。最后，我们的框架自然地提出了一个组合规则，它是实现失真3的有力候选，这也是在最近的工作中提出的。我们证明了3的畸变界可以从我们提出的三个组合猜想中的任何一个得到。
---
英文标题：
《An Analysis Framework for Metric Voting based on LP Duality》
---
作者：
David Kempe
---
最新提交年份：
2019
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Computer Science        计算机科学
二级分类：Discrete Mathematics        离散数学
分类描述：Covers combinatorics, graph theory, applications of probability. Roughly includes material in ACM Subject Classes G.2 and G.3.
涵盖组合学，图论，概率论的应用。大致包括ACM学科课程G.2和G.3中的材料。
--
一级分类：Economics        经济学
二级分类：Theoretical Economics        理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--

---
英文摘要：
  Distortion-based analysis has established itself as a fruitful framework for comparing voting mechanisms. m voters and n candidates are jointly embedded in an (unknown) metric space, and the voters submit rankings of candidates by non-decreasing distance from themselves. Based on the submitted rankings, the social choice rule chooses a winning candidate; the quality of the winner is the sum of the (unknown) distances to the voters. The rule's choice will in general be suboptimal, and the worst-case ratio between the cost of its chosen candidate and the optimal candidate is called the rule's distortion. It was shown in prior work that every deterministic rule has distortion at least 3, while the Copeland rule and related rules guarantee worst-case distortion at most 5; a very recent result gave a rule with distortion $2+\sqrt{5} \approx 4.236$.   We provide a framework based on LP-duality and flow interpretations of the dual which provides a simpler and more unified way for proving upper bounds on the distortion of social choice rules. We illustrate the utility of this approach with three examples. First, we give a fairly simple proof of a strong generalization of the upper bound of 5 on the distortion of Copeland, to social choice rules with short paths from the winning candidate to the optimal candidate in generalized weak preference graphs. A special case of this result recovers the recent $2+\sqrt{5}$ guarantee. Second, using this generalized bound, we show that the Ranked Pairs and Schulze rules have distortion $\Theta(\sqrt(n))$. Finally, our framework naturally suggests a combinatorial rule that is a strong candidate for achieving distortion 3, which had also been proposed in recent work. We prove that the distortion bound of 3 would follow from any of three combinatorial conjectures we formulate.
---
PDF链接：
https://arxiv.org/pdf/1911.07162