论文标题
除了最坏的情况之外：获胜者决心的半随机复杂性分析
Beyond the Worst Case: Semi-Random Complexity Analysis of Winner Determination
论文作者
论文摘要
获胜者确定的计算复杂性是计算社会选择中的经典和重要问题。以前基于最坏情况分析的工作已经确立了一些经典投票规则的胜利者决心，例如凯门尼，道奇和扬。 在本文中，我们通过半随机分析的角度来重新审视赢家确定的经典问题，这是最糟糕的平均分析分析，其中偏好是从对手选择的分布中产生的。在受推荐系统启发的自然类别的半随机模型下，我们证明，对于道奇森，Young和一些多获奖者规则，例如Chamberlin-Courant-Courant Rule和Monroe规则，获胜者的决心仍然很难。在另一种天然类型的半随机模型中，这是公正文化的扩展，我们表明赢得了胜利者的决心，对于凯门尼来说很难，但对于杜德格森来说很容易。这说明了凯门尼和道奇森之间有趣的分离。
The computational complexity of winner determination is a classical and important problem in computational social choice. Previous work based on worst-case analysis has established NP-hardness of winner determination for some classic voting rules, such as Kemeny, Dodgson, and Young. In this paper, we revisit the classical problem of winner determination through the lens of semi-random analysis, which is a worst average-case analysis where the preferences are generated from a distribution chosen by the adversary. Under a natural class of semi-random models that are inspired by recommender systems, we prove that winner determination remains hard for Dodgson, Young, and some multi-winner rules such as the Chamberlin-Courant rule and the Monroe rule. Under another natural class of semi-random models that are extensions of the Impartial Culture, we show that winner determination is hard for Kemeny, but is easy for Dodgson. This illustrates an interesting separation between Kemeny and Dodgson.
