2010/07/11 by Piotr Faliszewski, Edith Hemaspaandra, Faliszewski, Piotr +3 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #F.1.3 #F.2.2 #FOS: Computer and information sciences #I.2.11 #Internet Traffic Analysis and Secure E-voting #Multiagent Systems (cs.MA) #Network Security and Intrusion Detection
paper · pdf · doi:10.48550/arxiv.1007.1800
openalex publication_date 2010/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks on elections---attempts to improve the election outcome by such actions as adding/deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i.e., multimode) attack. We do so to more realistically capture the richness of real-life settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks, and by constructing polynomial-time multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time.