Dichotomy for Voting Systems
<|reference_start|>Dichotomy for Voting Systems: 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.<|reference_end|>
@article{hemaspaandra2005dichotomy,
    title={Dichotomy for Voting Systems},
    author={Edith Hemaspaandra and Lane A. Hemaspaandra},
    journal={arXiv preprint arXiv:cs/0504075},
    year={2005},
    number={URCS-TR-2005-861},
    archivePrefix={arXiv},
    eprint={cs/0504075},
    primaryClass={cs.GT cs.CC cs.MA}
}