Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Control complexity in Bucklin and fallback voting: An experimental analysis

Erdelyi, Gabor, Fellows, Michael R., Rothe, Jorg and Schend, Lena (2015). Control complexity in Bucklin and fallback voting: An experimental analysis. Journal of Computer and System Sciences,81(4):661-670.

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

IRMA ID 84373604xPUB68
Title Control complexity in Bucklin and fallback voting: An experimental 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-84924952439
Start Page 661
End Page 670
Total Pages 10
Place of Publication United States
Publisher Academic Press
HERDC Category C1 - Journal Article (DIISR)
Abstract Control in elections models situations in which an external actor tries to change the outcome of an election by restructuring the election itself. The corresponding decision problems have been shown NP-hard for a variety of voting systems. In particular, in our companion paper [16], we have shown that fallback and Bucklin voting are resistant (in terms of NP-hardness) to almost all of the common types of control. While NP-hardness results for manipulation (another way of tampering with the outcomes of elections) have been challenged experimentally (see, e.g., the work of Walsh [38] and [37]), such an experimental approach is sorely missing for control. We for the first time tackle NP-hard control problems in an experimental setting. Our experiments allow a more fine-grained analysis and comparison—across various control scenarios, vote distribution models, and voting systems—than merely stating NP-hardness for all these control problems.
Keywords Computational social choice
Control complexity
Bucklin voting
Fallback voting
Experimental analysis
Election systems
DOI http://dx.doi.org/10.1016/j.jcss.2014.11.003   (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: 5 Abstract Views  -  Detailed Statistics
Created: Tue, 26 Jul 2016, 12:59:21 CST