Authors: Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra
Abstract
While manipulation and bribery have been extensively studied in the context of weighted voting, the complexity of electoral control—altering election outcomes by adding or deleting voters—has remained largely unexplored. This paper addresses this gap by analyzing the computational complexity of weighted voter control across various voting rules. We establish a comprehensive taxonomy of results, ranging from polynomial-time algorithms to NP-completeness proofs. Furthermore, for several NP-complete cases, we provide polynomial-time approximation algorithms, demonstrating that even when exact solutions are hard to find, effective "near-optimal" control is often achievable.
Introduction
In computational social choice, the robustness of a voting system is often measured by its resistance to manipulative attacks. These attacks generally fall into three categories: manipulation (voters misreporting preferences), bribery (an external agent paying voters to change their votes), and control (an authority changing the election's structure).
While the first two have been studied extensively in weighted settings—where voters possess different weights, such as in corporate shareholding or the US Electoral College—the study of voter control in weighted elections has been surprisingly neglected. This paper fills this critical void, investigating how difficult it is for a central authority to ensure a preferred candidate's victory by adding or deleting weighted voters.
The Mechanics of Weighted Voter Control
The study focuses on two primary types of constructive control:
- Control by Adding Voters (WCCAV): The goal is to select a subset of voters from a pool of potential additions to ensure a specific candidate wins.
- Control by Deleting Voters (WCCDV): The goal is to remove a subset of existing voters to ensure a specific candidate wins.
In a weighted election, each voter $i$ has a weight $w_i$, and their preferences are counted according to this weight. This added dimension significantly complicates the search for an optimal set of voters to add or delete, often transforming "easy" problems into computationally intractable ones.
Complexity Results and the $t$-approval Threshold
The authors utilize tools from computational complexity theory, such as reductions from the Partition and Exact Cover by 3-Sets problems, to map the landscape of electoral control. A key finding is that weighted control is frequently more difficult than weighted manipulation. For instance, under the 3-candidate Llull rule, manipulation is in P, but voter control is NP-complete.
For scoring rules, the paper identifies a clear threshold. For a fixed number of candidates, $t$-approval (where voters select their top $t$ candidates) remains easy to control. However, once the number of candidates is unbounded or more complex rules like the Borda count are used, the problem typically becomes NP-complete.
Complexity Taxonomy for Weighted Voter Control
| Voting Rule | Control by Adding (WCCAV) | Control by Deleting (WCCDV) |
|---|---|---|
| Plurality | Easy (P) | Easy (P) |
| $t$-approval (fixed $m$) | Easy (P) | Easy (P) |
| Borda Count | NP-complete | NP-complete |
| Condorcet Rules | NP-hard | NP-hard |
| 2-approval (unbounded $m$) | Easy (P) | NP-complete |
Approximation Algorithms: The Greedy Approach
Recognizing that NP-completeness is not always a total defense, the authors explore approximation algorithms for the "hard" cases. They establish a formal link between electoral control and the Weighted Multicover (WMC) problem, a classic challenge in combinatorial optimization.
By adapting WMC techniques, they develop the Greedy by Weight (GBW) algorithm. For $t$-approval and $t$-veto, this algorithm provides a guaranteed $t$-approximation factor. This means that if the goal is to add the minimum number of voters to win, the greedy approach will find a set no larger than $t$ times the optimal size. This result suggests that while finding the perfect attack might be hard, finding a highly effective one is often computationally feasible.
Conclusion and Future Directions
This research provides the first systematic study of weighted voter control, offering a definitive map of which systems are naturally resistant to such structural manipulation. The findings highlight that while weights generally increase the complexity of control, they also open the door for approximation strategies that bypass traditional complexity-based defenses.
Future work remains in expanding these results to candidate control (adding or deleting candidates) and exploring approximation bounds for more sophisticated rules like Copeland or Borda. Additionally, while this paper focuses on constructive control, the nuances of destructive control (ensuring a candidate loses) in weighted environments warrant further investigation.
Summary updated