Dichotomy for Voting Systems

Simple item page
dc.creatorHemaspaandra, Edith
dc.creatorHemaspaandra, Lane A.
dc.date2005-04-15
dc.date.accessioned2026-07-07T03:22:54Z
dc.date.available2026-07-07T03:22:54Z
dc.descriptionScoring protocols are a broad class of voting systems. Each is defined by a vector $(α_1,α_2,...,α_m)$, $α_1 \geq α_2 \geq >... \geq α_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 \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.
dc.identifierhttps://arxiv.org/abs/cs/0504075
dc.identifierhttp://arxiv.org/abs/cs/0504075
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32732
dc.subjectComputer Science and Game Theory
dc.subjectComputational Complexity
dc.subjectMultiagent Systems
dc.subjectI.2.11; F.1.3; F.2.2
dc.titleDichotomy for Voting Systems
dc.typetext

Files

Collections

arXiv