Piotr Faliszewski, Edith Hemaspaandra, Lane Hemaspaandra, Joerg Rothe
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, and Trick 1992). An election system in which such an agent's computational task is NP-hard is said to be resistant to the given type of control. Aside from election systems with an NP-hard winner problem, the only systems known to be resistant to all the standard control types are highly artificial election systems created by hybridization (Hemaspaandra, Hemaspaandra, and Rothe 2007). 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 natural election system whose winner problem is in P. In addition, we show that Llull and Copeland voting are very broadly resistant to bribery attacks, and we integrate the potential irrationality of voter preferences into many of our results.
Subjects: 7.1 Multi-Agent Systems; 9.2 Computational Complexity
Submitted: Apr 23, 2007