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.

Paper: https://arxiv.org/abs/2010.13020

Founded in 1979, the Association for the Advancement of Artificial Intelligence (AAAI) (formerly the American Association for Artificial Intelligence) is a nonprofit scientific society devoted to advancing the scientific understanding of the mechanisms underlying thought and intelligent behavior and their embodiment in machines. AAAI aims to promote research in, and responsible use of, artificial intelligence. AAAI also aims to increase public understanding of artificial intelligence, improve the teaching and training of AI practitioners, and provide guidance for research planners and funders concerning the importance and potential of current AI developments and future directions.

The 35th AAAI Conference on Artificial Intelligence (AAAI-21) will be held virtually February 2-9, 2021.