Introduction
In the field of computational social choice, the integrity of voting systems is often measured by their resistance to manipulation. A common form of manipulation is control, where an election "chair" attempts to alter the outcome by changing the structure of the election—for instance, by adding or removing voters or candidates. A voting system is considered resistant if the control problem is NP-hard, providing a computational barrier against such interference. Conversely, if a control strategy can be found in polynomial time, the system is deemed vulnerable.
This paper focuses on the Borda Count, a widely used and "natural" voting system where candidates receive points based on their rank in each voter's preference list. Despite its popularity, several gaps remained in our understanding of its complexity. This research settles seven open problems, distinguishing between offline control (where all information is known upfront) and online control (where candidates appear sequentially).
Methodology
The researchers utilized standard computational complexity proofs to categorize these problems:
- For Offline Resistance: The authors employed polynomial-time reductions from known NP-complete problems. They reduced Exact Cover by 3-Sets (X3C) to prove the hardness of deleting voters, PARTITION for partitioning voters, and 3SAT for partitioning candidates.
- For Online Vulnerability: The authors developed polynomial-time algorithms based on a "maximin" strategy. These algorithms determine if a preferred candidate can be guaranteed a win regardless of how future, unrevealed candidates are ranked, essentially checking if any "bad" candidate can overcome their current deficit in the worst-case future scenario.
Key Results: Offline Resistance
The paper proves that the Borda Count is resistant to several sophisticated forms of offline manipulation. Specifically, it establishes that constructive control by deleting voters (a model for vote suppression), partition of voters (a model for gerrymandering), and run-off partition of candidates are all NP-hard.
As shown in the table above, these results fill critical gaps in the Borda complexity landscape, confirming that the system possesses inherent computational defenses against these specific structural attacks.
Key Results: Online Vulnerability
In a surprising contrast to the offline results, the paper finds that Borda is vulnerable to various forms of online control. In scenarios where candidates are introduced one by one and the chair must make immediate decisions (e.g., whether to delete a candidate) without full knowledge of future arrivals, the control problem becomes computationally easy (solvable in polynomial time).
The authors provide efficient algorithms for four online scenarios:
- Constructive and Destructive Control by Deleting Candidates (CCDC, DCDC)
- Constructive and Destructive Control by Adding Candidates (CCAC, DCAC)
This is a significant finding because previous research on online control often relied on "artificial" voting systems designed specifically to be hard. This work shows that for a natural system like Borda, the transition to an online setting can actually simplify the chair's computational task.
Conclusion and Future Work
By settling these seven problems, the paper provides a more complete picture of the Borda Count's robustness. While it is resistant to complex offline structural changes, its vulnerability in online settings highlights a potential weakness in sequential election processes.
Future research directions include exploring the "Ties-Promote" (TP) model for partitions, which remains an open question for Borda, and seeking a general "dichotomy result" that could predict the resistance or vulnerability of all scoring protocols across all types of control.
Summary updated