摘要翻译：
在度量空间上基于失真的社会选择规则分析中，人们假定所有投票者和候选人共同嵌入在一个公共度量空间中。选民按不递减的距离对候选人进行排序。该机制只接收这个顺序（比较）信息，应该选择一个与所有选民的距离之和近似最小的候选人。众所周知，虽然科普兰规则和相关规则保证失真最多为5，但许多其他标准投票规则，如多数、否决或$k$-批准，失真在$n$-候选人的数量中无限增长。多数、否决或$k$-与所有已知会实现持续扭曲的确定性社会选择规则相比，小$k$的批准需要更少的选民沟通。这促使我们研究确定性社会选择规则中的扭曲和交流量之间的权衡。我们证明了任何一轮确定性投票机制，其中每个选民只交流她在给定的$k$位置集合中排名的候选人，至少有$\frac{2n-k}{k}$失真；我们给出了一个实现$O(N/K)$的上界的机制，它与下界匹配到一个常数。对于更一般的通信有界投票机制，其中每个投票者通信$B$比特关于她的排名的信息，我们给出了失真的一个稍弱的下限$\omega(N/B)$。对于随机机制，众所周知，随机独裁实现的预期失真严格小于3，几乎与任何只接受每个选民的最优选择的随机机制的下界$3-\\frac{2}{n}$相匹配。我们通过给出一个简单的随机社会选择规则来弥补这一差距，该规则只使用每个选民的第一选择，并实现了预期的扭曲$3-\frac{2}{n}$。
---
英文标题：
《Communication, Distortion, and Randomness in Metric Voting》
---
作者：
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.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--

---
英文摘要：
  In distortion-based analysis of social choice rules over metric spaces, one assumes that all voters and candidates are jointly embedded in a common metric space. Voters rank candidates by non-decreasing distance. The mechanism, receiving only this ordinal (comparison) information, should select a candidate approximately minimizing the sum of distances from all voters. It is known that while the Copeland rule and related rules guarantee distortion at most 5, many other standard voting rules, such as Plurality, Veto, or $k$-approval, have distortion growing unboundedly in the number $n$ of candidates.   Plurality, Veto, or $k$-approval with small $k$ require less communication from the voters than all deterministic social choice rules known to achieve constant distortion. This motivates our study of the tradeoff between the distortion and the amount of communication in deterministic social choice rules.   We show that any one-round deterministic voting mechanism in which each voter communicates only the candidates she ranks in a given set of $k$ positions must have distortion at least $\frac{2n-k}{k}$; we give a mechanism achieving an upper bound of $O(n/k)$, which matches the lower bound up to a constant. For more general communication-bounded voting mechanisms, in which each voter communicates $b$ bits of information about her ranking, we show a slightly weaker lower bound of $\Omega(n/b)$ on the distortion.   For randomized mechanisms, it is known that Random Dictatorship achieves expected distortion strictly smaller than 3, almost matching a lower bound of $3-\frac{2}{n}$ for any randomized mechanism that only receives each voter's top choice. We close this gap, by giving a simple randomized social choice rule which only uses each voter's first choice, and achieves expected distortion $3-\frac{2}{n}$.
---
PDF链接：
https://arxiv.org/pdf/1911.08129