Low-Distortion Social Welfare Functions
Low-Distortion Social Welfare Functions
复制标题
DOI：
10.1609/aaai.v33i01.33011788
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Gerdus Benade;Ariel D. Procaccia;Mingda Qiao
中科院分区：
文献类型：
--
作者：
Gerdus Benade;Ariel D. Procaccia;Mingda Qiao
隐式功利主义投票的工作主张设计的偏好聚合方法，最大限度地提高功利主义的社会福利方面的潜在效用函数，仅基于观察到的排名的替代品。这种方法已经成功地用于帮助人们选择一个选项或选项的子集，但以前不清楚如何将相同的方法应用于社会福利函数的设计，其中期望的输出是排名。我们建议解决这个问题，假设选民的排名效用是由未知的权重和未知的效用函数，其中，此外，有一个组合（次加性）的结构。尽管极端缺乏选民的偏好信息，我们表明，它是可以选择的排名，使他们的社会福利和最佳排名，所谓的失真之间的最坏情况下的差距，是不大于（多对数因子）比与更简单的问题相关的失真。通过实验，我们确定了实际的方法，实现平均接近最优的社会福利。
Work on implicit utilitarian voting advocates the design of preference aggregation methods that maximize utilitarian social welfare with respect to latent utility functions, based only on observed rankings of the alternatives. This approach has been successfully deployed in order to help people choose a single alternative or a subset of alternatives, but it has previously been unclear how to apply the same approach to the design of social welfare functions, where the desired output is a ranking. We propose to address this problem by assuming that voters’ utilities for rankings are induced by unknown weights and unknown utility functions, which, moreover, have a combinatorial (subadditive) structure. Despite the extreme lack of information about voters’ preferences, we show that it is possible to choose rankings such that the worst-case gap between their social welfare and that of the optimal ranking, called distortion, is no larger (up to polylogarithmic factors) than the distortion associated with much simpler problems. Through experiments, we identify practical methods that achieve nearoptimal social welfare on average.