Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Control complexity in Bucklin and fallback voting: A theoretical analysis

Erdelyi, Gabor, Fellows, Michael R., Rothe, Jorg and Schend, Lena (2015). Control complexity in Bucklin and fallback voting: A theoretical analysis. Journal of Computer and System Sciences,81(4):632-660.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

IRMA ID 84373604xPUB67
Title Control complexity in Bucklin and fallback voting: A theoretical analysis
Author Erdelyi, Gabor
Fellows, Michael R.
Rothe, Jorg
Schend, Lena
Journal Name Journal of Computer and System Sciences
Publication Date 2015
Volume Number 81
Issue Number 4
ISSN 0022-0000   (check CDU catalogue  open catalogue search in new window)
Scopus ID 2-s2.0-84924939951
Start Page 632
End Page 660
Total Pages 29
Place of Publication United States
Publisher Academic Press
HERDC Category C1 - Journal Article (DIISR)
Abstract Electoral control models ways of changing the outcome of an election via such actions as adding, deleting, or partitioning either candidates or voters. To protect elections from such control attempts, computational complexity has been used to establish so-called resistance results. We show that fallback voting, an election system proposed by Brams and Sanver [12] to combine Bucklin with approval 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 and show that it performs almost as well as fallback voting in terms of control resistance. Furthermore, we investigate the parameterized control complexity of Bucklin and fallback voting, according to several parameters that are often likely to be small for typical instances. In a companion paper [28], we challenge our worst-case complexity results from an experimental point of view.
Keywords Computational social choice
Control complexity
Bucklin voting
Fallback voting
Parameterized complexity
Election systems
DOI http://dx.doi.org/10.1016/j.jcss.2014.11.002   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 9 Abstract Views  -  Detailed Statistics
Created: Tue, 26 Jul 2016, 12:59:18 CST