论文标题
计算Kemeny和Slater排名的平滑复杂性
The Smoothed Complexity of Computing Kemeny and Slater Rankings
论文作者
论文摘要
在共同投票规则下，赢家确定的计算复杂性是计算社会选择领域的经典和基本话题。先前的工作已经确定了一些普遍研究的投票规则，尤其是凯门尼规则和斯莱特规则，确定了获胜者的决心。在最近的蓝色纸张论文中，鲍梅斯特（Baumeister），霍格雷（Hogrebe）和罗斯（Rothe，2020年）质疑NP硬度在社会选择中最严重的案例性质的相关性，并提议在Bllaser和Manthey（2015）（2015）的框架下进行平滑的复杂性分析（Spielman and Teng 2009）。 在本文中，我们为投票中的赢家确定开发了第一个平滑的复杂性结果。我们通过证明矛盾的结果来说明Blaser and Manthey（2015）在社会选择环境中平滑复杂性框架的不合适性，该结果表明，根据其定义，指数级的蛮力蛮力搜索算法是平滑的。然后，我们使用经典的平滑复杂性分析证明了Kemeny和Slater的平滑硬度，并证明了Kemeny的参数化典型案例平滑性结果。总体而言，我们的结果表明，计算社会选择中平滑的复杂性分析是一个具有挑战性且富有成果的话题。
The computational complexity of winner determination under common voting rules is a classical and fundamental topic in the field of computational social choice. Previous work has established the NP-hardness of winner determination under some commonly-studied voting rules, especially the Kemeny rule and the Slater rule. In a recent blue-sky paper, Baumeister, Hogrebe, and Rothe (2020) questioned the relevance of the worst-case nature of NP-hardness in social choice and proposed to conduct smoothed complexity analysis (Spielman and Teng 2009) under Blaser and Manthey (2015)'s framework. In this paper, we develop the first smoothed complexity results for winner determination in voting. We illustrate the inappropriateness of Blaser and Manthey (2015)'s smoothed complexity framework in social choice contexts by proving a paradoxical result, which states that the exponential-time brute force search algorithm is smoothed poly-time according to their definition. We then prove the smoothed hardness of Kemeny and Slater using the classical smoothed complexity analysis, and prove a parameterized typical-case smoothed easiness result for Kemeny. Overall, our results show that smoothed complexity analysis in computational social choice is a challenging and fruitful topic.
