Control Complexity in Bucklin, Fallback, and Plurality Voting: An Experimental Approach

Details Control Complexity in Bucklin, Fallback, and Plurality Voting: An Experimental Approach Control Complexity in Bucklin, Fallback, and Plurality Voting: An Experimental Approach

2012-03-18

arxiv.org/abs/1203.3967v1

Computer Science

Computer Science and Game Theory

311 pages, numerous figures, a short version appears in the proceeedings of the 11th International Symposium on Experimental A

Scientific paper

Walsh [Wal10, Wal09], Davies et al. [DKNW10, DKNW11], and Narodytska et al. [NWX11] studied various voting systems empirically and showed that they can often be manipulated effectively, despite their manipulation problems being NP-hard. Such an experimental approach is sorely missing for NP-hard control problems, where control refers to attempts to tamper with the outcome of elections by adding/delet-ing/partitioning either voters or candidates. We experimentally tackle NP-hard control problems for Bucklin and fallback voting, which among natural voting systems with efficient winner determination are the systems currently known to display the broadest resistance to control in terms of NP-hardness [ER10, EPR11]. We also investigate control resistance experimentally for plurality voting, one of the first voting systems analyzed with respect to electoral control [BTT92, HHR07]. Our findings indicate that NP-hard control problems can often be solved effectively in practice. Moreover, 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.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-617739