Control complexity in Bucklin and fallback voting: An experimental analysis

• Electoral control models ways of changing the outcome of an election via adding, deleting, or partitioning candidates or voters.
• We tackle NP-hard control problems for Bucklin and fallback elections in an experimental setting.
• While NP-hard manipulation problems have been challenged experimentally, this is the first such study for electoral control.
• Our experiments allow a more fine-grained analysis and comparison of the computational hardness of control problems.

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.