Control in the presence of manipulators: cooperative and competitive cases
- PDF / 477,368 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 100 Downloads / 220 Views
Control in the presence of manipulators: cooperative and competitive cases Zack Fitzsimmons1
· Edith Hemaspaandra2
· Lane A. Hemaspaandra3
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Control and manipulation are two of the most studied types of attacks on elections. In this paper, we study the complexity of control attacks on elections in which there are manipulators. We study both the case where the “chair” who is seeking to control the election is allied with the manipulators, and the case where the manipulators seek to thwart the chair. In the latter case, we see that the order of play substantially influences the complexity. We prove upper bounds, holding over every election system with a polynomial-time winner problem, for all standard control cases, and some of these bounds are at the second or third level of the polynomial hierarchy, and we provide matching lower bounds to prove these tight. Nonetheless, for important natural systems the complexity can be much lower. We prove that for approval and plurality elections, the complexity of even competitive clashes between a controller and manipulators falls far below those high bounds, even as low as polynomial time. Yet for a Borda-voting case we show that such clashes raise the complexity unless NP = coNP. Keywords Computational social choice · Control · Manipulation · Complexity
Earlier versions of this paper [31,34] were presented at the Twenty-Third International Joint Conference on Artificial Intelligence and the Fifth International Workshop on Computational Social Choice. This work was done in part while Zack Fitzsimmons was at RIT and while Edith Hemaspaandra and Lane A. Hemaspaandra were on sabbatical visits to ETH-Zürich and the University of Düsseldorf.
B
Zack Fitzsimmons [email protected] Edith Hemaspaandra [email protected] Lane A. Hemaspaandra http://www.cs.rochester.edu/u/lane
1
Department of Mathematics and Computer Science, College of the Holy Cross, Worcester, MA 01610, USA
2
Department of Computer Science, Rochester Institute of Technology, Rochester, NY 14623, USA
3
Department of Computer Science, University of Rochester, Rochester, NY 14627, USA 0123456789().: V,-vol
123
52
Page 2 of 32
Autonomous Agents and Multi-Agent Systems
(2020) 34:52
1 Introduction Elections are an important tool in reaching decisions, in both human and online settings. Regarding online settings, elections have been proposed in such varied, multiagent-systems settings as planning, recommender systems/collaborative filtering, and web spam reduction [18,21,37,58]. With the growing importance of the online world and multiagent systems, the use of elections in computer-based settings will but increase. Unfortunately, given the relentless growth in the power of computers, it is natural to worry that computers will also be increasingly brought to bear in planning manipulative attacks on elections. Indeed, this is one of the central concerns of the relatively young multiagent systems subarea known as computational social
Data Loading...
