Today I read a paper titled “Dichotomy for Voting Systems”
The abstract is:
Scoring protocols are a broad class of voting systems.
Each is defined by a vector $(\alpha_1,\alpha_2,…,\alpha_m)$, $\alpha_1 \geq \alpha_2 \geq >…
\geq \alpha_m$, of integers such that each voter contributes $\alpha_1$ points to his/her first choice, $\alpha_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 $||\{\alpha_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.