Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments

Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier

Introduction

Traditional social choice theory evaluates the robustness of an election result using the Margin of Victory—the minimum number of changes (swaps or shifts) required to alter the outcome. This metric essentially identifies the "cheapest bribery" scenario. However, this deterministic approach fails to capture probabilistic robustness: the likelihood that an outcome remains stable under random noise or voter "misrankings." This paper introduces a counting-based framework to quantify robustness by analyzing how many ways an election outcome can change within a given "swap radius" $r$.

Computational Complexity of Counting

The authors investigate the complexity of counting winning scenarios under #SWAP-BRIBERY and #SHIFT-BRIBERY. While determining if a winner can be changed is often computationally feasible (e.g., in P for Plurality), counting the number of such scenarios is significantly harder. The study establishes that #SWAP-BRIBERY for the Plurality rule is both #P-hard and #W[1]-hard with respect to the swap radius. This suggests that as the allowed noise increases, calculating exact robustness becomes exponentially difficult.

Experimental Analysis of Probabilistic Robustness

To circumvent the computational hardness of exact counting, the authors employ Monte Carlo sampling on synthetic datasets consisting of 800 elections with 10 candidates and 100 voters. They estimate $P_c(r)$, the probability that candidate $c$ wins after $r$ random swaps.

Figure 1: Probability of victory $P_c(r)$ as a function of swap radius $r$ for various candidates in Urn models.

As shown in Figure 1, the probability of victory for a winner (e.g., candidate 577 in Urn 0.01) can drop sharply even with a small swap radius, while other candidates' probabilities may temporarily increase. This visualization highlights that a candidate's lead is not always a guarantee of stability against random errors.

The Score-Robustness Gap

A central finding of the research is the "Score-Robustness Gap." While the cost of the "cheapest bribery" (optimal bribery) correlates strongly with the winner's score lead, the 50%-winner threshold—the swap distance at which a winner's chance of victory falls below 50%—does not.

Figure 6: Correlation between score difference and robustness metrics (optimal bribery vs. 50%-winner threshold) for Plurality and Borda rules.

Figure 6 illustrates this gap. In both Plurality and Borda rules, the optimal bribery (red dots) follows a predictable linear relationship with the score difference. In contrast, the 50%-winner threshold (black dots) shows significant variance. This indicates that a winner with a large point lead can still be "fragile," susceptible to being overturned by a collection of small, random misrankings that traditional metrics would overlook. Furthermore, Borda winners tend to be more robust than Plurality winners, as points are distributed across the entire ballot rather than just the top rank.

Conclusion

This work demonstrates that counting-based metrics provide a more nuanced view of election stability than simple score differences or minimum-cost bribery. By establishing the complexity of these counting problems and providing experimental evidence of the score-robustness gap, the authors highlight the need for probabilistic measures in evaluating the integrity of social choice outcomes. Future research may extend these findings to real-world preference data and explore exact algorithms for currently open complexity classes.

Summary updated

Abstract

We study the parameterized complexity of counting variants of Swap- and Shift-Bribery, focusing on the parameterizations by the number of swaps and the number of voters. Facing several computational hardness results, using sampling we show experimentally that Swap-Bribery offers a new approach to the robustness analysis of elections.
BibTeX
@inproceedings{boehmer2021winner,
  author = {Niclas Boehmer and Robert Bredereck and Piotr Faliszewski and Rolf Niedermeier},
  title = {{Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/8},
}
Figure