标题：How hard is control in multi-peaked elections: A parameterized study
作者：Yang, Yongjie ;Guo, Jiong
作者机构：[Yang, Yongjie ] Universität des Saarlandes, Campus E 1.7 (MMCI), Saarbrücken; D-66123, Germany;[Guo, Jiong ] Shandong University, School of 更多
会议名称：14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015
会议日期：4 May 2015 through 8 May 2015
来源：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
关键词：Condorcet; Copeland; Election control; Maximin; Multi-peaked; Parameterized complexity; Single-peaked generalization
摘要：We study the complexity of voting control problems in multi-peaked elections. In particular, we focus on the constructive/destructive control by adding/deleting votes under Condorcet, Maximin and Copeland voting systems. We show that the p/P-hardness of these problems (except for the destructive control by adding/deleting votes under Condorcet, which is polynomial-time solvable in the general case) hold even in n-peaked elections with n being a very small constant. Furthermore, from the parameterized complexity point of view, our reductions actually show that these problems are W-hard in n-peaked elections with n 3, 4, with respect to the number of added/deleted votes. Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.