Dichotomy for Voting Systems

Abstract

Scoring protocols are a broad class of voting systems. Each is defined by a vector $(α_1,α_2,...,α_m)$, $α_1 \geq α_2 \geq >... \geq α_m$, of integers such that each voter contributes $α_1$ points to his/her first choice, $α_2$ points to his/her second choice, and so on, and any candidate receiving the most points is a winner. What is it about scoring-protocol election systems that makes some have the desirable property of being NP-complete to manipulate, while others can be manipulated in polynomial time? We find the complete, dichotomizing answer: Diversity of dislike. Every scoring-protocol election system having two or more point values assigned to candidates other than the favorite--i.e., having $||\{α_i \condition 2 \leq i \leq m\}||\geq 2$--is NP-complete to manipulate. Every other scoring-protocol election system can be manipulated in polynomial time. In effect, we show that--other than trivial systems (where all candidates alway tie), plurality voting, and plurality voting's transparently disguised translations--\emph{every} scoring-protocol election system is NP-complete to manipulate.