Manipulation of copeland elections

Abstract

We resolve an open problem regarding the complexity of unweighted coalitional manipulation, namely, the complexity of Copeland α-manipulation for α ∈{0, 1}. Copeland α, 0 ≤ α ≤ 1, is an election system where for each pair of candidates we check which one is preferred by more voters (i.e., we conduct a head-to-head majority contest) and we give one point to this candidate and zero to the other. However, in case of a tie both candidates receive α points. In the end, candidates with most points win. It is known [13] that Copeland α-manipulation is NP-complete for all rational α’s in (0, 1) −{0.5} (i.e., for all the reasonable cases except the three truly interesting ones). In this paper we show that the problem remains NP-complete for α ∈{0, 1}. In addition, we resolve the complexity of Copeland α-manipulation for each rational α ∈ [0, 1] for the case of irrational voters.