Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties
Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties
复制标题
社会选择规则的度量扭曲：下界和公平性
DOI：
10.1145/3033274.3085138
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Munagala, Kamesh
中科院分区：
文献类型：
--
作者：
Goel, Ashish;Krishnaswamy, Anilesh K.;Munagala, Kamesh
我们在功利主义扭曲框架下研究社会选择规则，并对代理的替代成本进行了额外的度量假设。在这种方法中，这些成本是由所有代理加上备选方案的集合的基本度量给出的。社会选择规则只能接触到行为主体的有序偏好，而不能接触到诱发这些偏好的潜在基数成本。然后将扭曲定义为由现有机制选择的替代方案的社会成本（通常是代理成本的总和）与由全知算法选择的最优替代方案之间的比率。因此，社会选择规则的最坏情况是，在不知道潜在成本的情况下，衡量它与最优选择的接近程度。在这个模型下，据推测，众所周知的加权比赛规则排名赛（rank Pairs）最多实现了3的扭曲（Anshelevich et al. 2015）。我们通过构造一个实例序列来证明排序对的最坏情况失真至少为5。我们关于排名配对的最坏情况失真的下界与先前已知的Copeland规则的上界相匹配，证明了在最坏情况下，更简单的Copeland规则至少与排名配对一样好。只要我们受限于（加权或未加权）锦标赛规则，我们就可以证明随机化无法帮助实现小于3的预期最坏情况失真。利用扭曲框架内的近似多数化概念，我们证明了Copeland和randomrandomdictatorship实现了较低的常数因子公平比率（分别为5和3），这是对成本总和和单个最大成本目标的类似结果的相当大的推广。除此之外，我们还概述了该领域进一步研究的几个有趣方向。
We study social choice rules under the utilitarian distortion framework, with an additional metric assumption on the agents' costs over the alternatives. In this approach, these costs are given by an underlying metric on the set of all agents plus alternatives. Social choice rules have access to only the ordinal preferences of agents but not the latent cardinal costs that induce them. Distortion is then defined as the ratio between the social cost (typically the sum of agent costs) of the alternative chosen by the mechanism at hand, and that of the optimal alternative chosen by an omniscient algorithm. The worst-case distortion of a social choice rule is, therefore, a measure of how close it always gets to the optimal alternative without any knowledge of the underlying costs. Under this model, it has been conjectured that Ranked Pairs, the well-known weighted-tournament rule, achieves a distortion of at most 3 (Anshelevich et al. 2015). We disprove this conjecture by constructing a sequence of instances which shows that the worst-case distortion of Ranked Pairs is at least 5. Our lower bound on the worst-case distortion of Ranked Pairs matches a previously known upper bound for the Copeland rule, proving that in the worst case, the simpler Copeland rule is at least as good as Ranked Pairs. And as long as we are limited to (weighted or unweighted) tournament rules, we demonstrate that randomization cannot help achieve an expected worst-case distortion of less than 3. Using the concept of approximate majorization within the distortion framework, we prove that Copeland and Randomized Dictatorship achieve low constant factor fairness-ratios (5 and 3 respectively), which is a considerable generalization of similar results for the sum of costs and single largest cost objectives. In addition to all of the above, we outline several interesting directions for further research in this space.
登录
查看更多内容
DOI：
--
发表时间：
1997
期刊：
Lecture Notes in Computer Science
影响因子：
--
作者：
John A. Papalas;A. Proia
通讯作者：
A. Proia
尽管沟通有限，投票几乎使社会福利最大化
影响因子：
14.4
作者：
I. Caragiannis;Ariel D. Procaccia
通讯作者：
Ariel D. Procaccia
影响因子：
0.9
作者：
S. Barberà
通讯作者：
S. Barberà
通过凹利润或凸成本的近似多数化同时优化
影响因子：
1.1
作者：
Ashish Goel;A. Meyerson
通讯作者：
A. Meyerson
Maximin、leximin 和保护标准：特征和比较
DOI：
--
发表时间：
1988
期刊：
影响因子：
--
作者：
S. Barbara;M. Jackson
通讯作者：
M. Jackson