Copeland Voting: Ties Matter

We study the complexity of manipulation for a family of election systems derived from Copeland voting via introducing a parameter α that describes how ties in head-to-head contests are valued. We show that the thus obtained problem of manipulation for unweighted Copelandα elections is NP-complete even if the size of the manipulating coalition is limited to two. Our result holds for all rational values of α such that 0 < α < 1 except for α = 1 2. Since it is well known that manipulation via a single voter is easy for Copeland, our result is the first one where an election system originally known to be vulnerable to manipulation via a single voter is shown to be resistant to manipulation via a coalition of a constant number of voters. We also study the complexity of manipulation for Copelandα for the case of a constant number of candidates. We show that here the exact complexity of manipulation often depends closely on the α: Depending on whether we try to make our favorite candidate a winner or a unique winner and whether α is 0, 1 or between these values, the problem of weighted manipulation for Copelandα with three candidates is either in P or is NP-complete. Our results show that ways in which ties are treated in an election system, here Copeland voting, can be crucial to establishing complexity results for this system.

Authors

• Piotr Faliszewski AGH University
• Edith Hemaspaandra
• Henning Schnoor University of Kiel

Keywords

• preferences
• computational complexity
• multiagent systems