Control complexity in bucklin, fallback, and plurality voting: An experimental approach. In: Experimental Algorithms

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 ef-fectively, 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/deleting/partitioning either voters or candidates. We ex-perimentally tackle NP-hard control problems for Bucklin and fallback voting. Among natural voting systems with efficient winner determination, fallback voting is currently known to display the broadest resistance to control in terms of NP-hardness, and Bucklin voting has been shown to behave almost as well in terms of control resistance [ER10, EPR11, EFPR11]. We also in-vestigate 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 prac-tice. 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. ∗This work was supported in part by DFG grants RO 1202/15-1 and RO 1202/12-1 (within the EUROCORES programme LogICC