2020/10/25 by Lirong Xia, Weiqiang Zheng, Xia, Lirong +1 · 3 citations
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Algorithm #Auction Theory and Applications #Computational Complexity (cs.CC) #Computational complexity theory #Computer Science and Game Theory (cs.GT) #Computer science #FOS: Computer and information sciences #Field (mathematics) #Game Theory and Voting Systems #Internet Traffic Analysis and Secure E-voting #Law #Mathematical economics #Mathematics #Parameterized complexity #Social choice theory #Theoretical computer science #Voting #cs.CC #cs.GT
paper · pdf · doi:10.48550/arxiv.2010.13020
published in arXiv (Cornell University) (Cornell University)
arxiv created 2020/10/25 · openalex publication_date 2020/10/25 · arxiv updated 2020/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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.