失真的计算方面
Computational Aspects of Distortion
Soroush Ebadian, Aris Filos-Ratsikas, Mohamad Latifian, Nisarg Shah
AI 速读 基于摘要
该论文为社会选择中的失真框架提出基于线性规划的最优随机决策算法，以及基于非凸二次规划计算随机位置评分规则精确失真的方法。
cs.GT
查看原文摘要
The distortion framework in social choice theory allows quantifying the efficiency of (randomized) selection of an alternative based on the preferences of a set of agents. We make two fundamental contributions to this framework. First, we develop a linear-programming-based algorithm for computing the optimal randomized decision on a given instance, which is simpler and faster than the state-of-the-art solutions. For practitioners who may prefer to deploy a classical decision-making rule over the aforementioned optimal rule, we develop an algorithm based on non-convex quadratic programming for computing the exact distortion of any (and the best) randomized positional scoring rule. For a small number of alternatives, we find that the exact distortion bounds are significantly better than the asymptotic upper bounds established in prior literature and lead to different recommendations on which rules to use. These results rely on a novel characterization of the instances yielding the worst distortion, which may be of independent interest.