Control in the Presence of Manipulators: Cooperative and Competitive Cases
Authors:
Preprint
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 we for a Borda-voting case show that such clashes raise the complexity unless NP = coNP.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Multimode Control Attacks on ElectionsJournal of Artificial Intelligence Research, 2011
- Using complexity to protect electionsCommunications of the ACM, 2010
- How Hard Is Bribery in Elections?Journal of Artificial Intelligence Research, 2009
- Hybrid Elections Broaden Complexity‐Theoretic Resistance to ControlMathematical Logic Quarterly, 2009
- Sincere‐Strategy Preference‐Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive ControlMathematical Logic Quarterly, 2009
- Llull and Copeland Voting Computationally Resist Bribery and Constructive ControlJournal of Artificial Intelligence Research, 2009
- When are elections with few candidates hard to manipulate?Journal of the ACM, 2007
- Anyone but him: The complexity of precluding an alternativeArtificial Intelligence, 2007
- The polynomial-time hierarchyTheoretical Computer Science, 1976