Llull and Copeland Voting Broadly Resist Bribery and Control

Abstract

Control of elections refers to attempts by an agent to, via such actions as addition/deletion/partition of candidates or voters, ensure that a given candidate wins (Bartholdi, Tovey, & Trick 1992). An election system in which such an agent’s computa-tional task is NP-hard is said to be resistant to the given type of control. Aside from election systems with an NP-hard win-ner problem, the only systems known to be resistant to all the standard control types are highly artificial election systems created by hybridization (Hemaspaandra, Hemaspaandra, & Rothe 2007b). In this paper, we prove that an election system developed by the 13th century mystic Ramon Llull and the well-studied Copeland election system are both resistant to all the standard types of (constructive) electoral control other than one variant of addition of candidates. This is the most comprehensive resistance to control yet achieved by any nat-ural election system whose winner problem is in P. In addi-tion, we show that Llull and Copeland voting are very broadly resistant to bribery attacks, and we integrate the potential ir-rationality of voter preferences into many of our results.