Computer Science – Computer Science and Game Theory
Scientific paper
2005-04-15
Computer Science
Computer Science and Game Theory
Scientific paper
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.
Hemaspaandra Edith
Hemaspaandra Lane A.
No associations
LandOfFree
Dichotomy for Voting Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dichotomy for Voting Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dichotomy for Voting Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-88732