Dichotomy for voting systems

摘要

Scoring protocols are a broad class of voting systems. Each is defined by a vector (α1,α2,…,αm), α1⩾α2⩾⋯⩾α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|2⩽i⩽m}‖⩾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—every scoring-protocol election system is NP-complete to manipulate.