Relating Metric Distortion and Fairness of Social Choice Rules
Relating Metric Distortion and Fairness of Social Choice Rules
复制标题
将度量扭曲与社会选择规则的公平性联系起来
DOI：
10.1145/3230654.3230658
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Krishnaswamy, Anilesh K.
中科院分区：
文献类型：
--
作者：
Goel, Ashish;Hulett, Reyna;Krishnaswamy, Anilesh K.
投票是许多重要决策的核心，尤其是政府官员的选举。投票或社会选择理论研究通过社会选择规则将代理人偏好聚集到单个集体决策中。通常，每个代理提交一个候选人的排名，社会选择规则将这些偏好的任何实例映射到一个或多个备选方案。但是我们如何选择社会选择规则呢？传统上，这些规则已经评估的基础上简单的公理标准，例如，多数赢家标准，但不幸的是，即使是小集公理可能无法同时满足。最近的一种方法超越了公理，对社会选择采取了功利主义的观点。在这个模型中，虽然代理人表示他们的偏好通过一个有序的排名，他们被假定为有潜在的基数偏好的替代品。在度量失真模型[1]中，我们假设代理人和替代品位于任意未知的度量空间中，并且代理人的替代品成本等于两者之间的距离。只有这个简单的假设，它已经表明，一些社会选择规则，如科普兰，可以实现一个恒定的因素失真，即最坏情况下的社会成本的比例选择的候选人的最佳候选人选择全知[1]。在度量失真框架内，我们还可以问一个社会选择规则在数量上有多“公平”。为此，我们考虑公平比[2]，这是一个同时的界限，在所有k，对所选候选人的k个最大代理成本的比率
Voting is at the core of many important decisions, not least the election of government officials. Voting, or social choice, theory studies the aggregation of agent preferences into a single collective decision via a social choice rule. Usually, each agent submits a ranking over the candidates, and a social choice rule maps any instance of these preferences to one or more alternatives. But how do we choose the social choice rule? Traditionally, these rules have been evaluated based on simple axiomatic criteria—eg, the majority winner criterion—but unfortunately even small sets of axioms can be impossible to satisfy simultaneously. A more recent approach goes beyond axioms to take a utilitarian view of social choice. In this model, although agents express their preferences via an ordinal ranking, they are assumed to have latent cardinal preferences over the alternatives. In the metric distortion model [1], we assume that the agents and alternatives lie in an arbitrary, unknown metric space, and an agent’s cost for an alternative equals the distance between the two. With only this simple assumption, it has been shown that some social choice rules, like Copeland, can achieve a constant factor distortion—that is, the worst-case ratio of the social cost of the chosen candidate to that of the optimal candidate chosen omnisciently [1]. Within the metric distortion framework, we can also ask how quantitatively “fair” a social choice rule is. To this end, we consider the fairness ratio [2], which is a simultaneous bound, over all k, on the ratio of the k largest agent costs for the chosen candidate
登录
查看更多内容
尽管沟通有限，投票几乎使社会福利最大化
影响因子：
14.4
作者：
I. Caragiannis;Ariel D. Procaccia
通讯作者：
Ariel D. Procaccia
影响因子：
0.9
作者：
S. Barberà
通讯作者：
S. Barberà
通过凹利润或凸成本的近似多数化同时优化
影响因子：
1.1
作者：
Ashish Goel;A. Meyerson
通讯作者：
A. Meyerson
影响因子：
3.7
作者：
Cabannes, Y
通讯作者：
Cabannes, Y
DOI：
10.1145/3033274.3085138
发表时间：
2017
期刊：
EC '17 Proceedings of the 2017 ACM Conference on Economics and Computation
影响因子：
--
作者：
Goel, Ashish;Krishnaswamy, Anilesh K.;Munagala, Kamesh
通讯作者：
Munagala, Kamesh