标题: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
出版年:2015
卷:3
页码:1729-1730
关键词: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[1]-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.
收录类别:EI;SCOPUS
Scopus被引频次:6
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84944682991&partnerID=40&md5=11cff66c079b17cc615d304eca180406
TOP