Control Complexity in Bucklin and Fallback Voting

Details Control Complexity in Bucklin and Fallback Voting Control Complexity in Bucklin and Fallback Voting

2011-03-11

arxiv.org/abs/1103.2230v1

Computer Science

Computational Complexity

44 pages; merges, extends, and supersedes the technical reports arXiv:1004.3398, arXiv:1004.3659, and arXiv:1005.4115

Scientific paper

Electoral control models ways of changing the outcome of an election via such actions as adding/deleting/partitioning either candidates or voters. These actions modify an election's participation structure and aim at either making a favorite candidate win ("constructive control") or prevent a despised candidate from winning ("destructive control"). To protect elections from such control attempts, computational complexity has been used to show that electoral control, though not impossible, is computationally prohibitive. We show that fallback voting, an election system proposed by Brams and Sanver to combine Bucklin with approval voting, is resistant to each of the common types of control except to destructive control by either adding or deleting voters. Thus fallback voting displays the broadest control resistance currently known to hold among natural election systems with a polynomial-time winner problem. We also study the control complexity of Bucklin voting itself and show that it behaves almost as good (possibly even as good) as fallback voting in terms of control resistance. As Bucklin voting is a special case of fallback voting, each resistance shown for Bucklin voting strengthens the corresponding resistance for fallback voting. Finally, we study the parameterized control complexity of Bucklin and fallback voting.

Affiliated with

Also associated with

No associations

Rating

Control Complexity in Bucklin and Fallback Voting 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 Control Complexity in Bucklin and Fallback Voting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Control Complexity in Bucklin and Fallback Voting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-430178