2005/04/15 by Edith Hemaspaandra, Hemaspaandra, Edith, Lane A. Hemaspaandra +1 · 2 citations
Computer Science · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Game Theory and Voting Systems #Internet Traffic Analysis and Secure E-voting #cs.CC #cs.GT #cs.MA
paper · pdf · doi:10.48550/arxiv.cs/0504075
arxiv created 2005/04/15 · arxiv updated 2009/12/01
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 \condition 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.