Abstract
This paper resolves 10 out of 11 previously open questions regarding the computational complexity of "control" in Borda elections. Through theoretical computer science proofs, the authors demonstrate that while the Borda Count is robust against an election chair attempting to force a specific candidate to win (constructive control), it is often vulnerable to attempts to make a candidate lose (destructive control). This work highlights a rare instance where the definition of a "winner"—unique versus nonunique—fundamentally changes the computational difficulty of the problem.
Introduction
In the field of Computational Social Choice, researchers investigate the susceptibility of voting systems to various forms of interference. One primary area of study is control, where an election chair uses their authority over the election's structure to manipulate the outcome. This can involve adding or deleting candidates, adding or deleting voters, or partitioning candidates and voters into sub-groups, such as primaries.
The Borda Count is a widely recognized voting system where voters rank candidates, and candidates receive points based on their position (e.g., in an $m$-candidate race, 1st place receives $m-1$ points, 2nd receives $m-2$, and so on). Despite its prominence, the "complexity map" for Borda was historically incomplete. This research aims to determine whether specific types of control are computationally "hard" (NP-hard), providing a natural barrier against attacks, or "easy" (Polynomial-time), meaning a chair could efficiently find a way to manipulate the result.
Methods
The authors utilize theoretical reductions to classify the complexity of the remaining open cases. By reducing known NP-complete problems—specifically X3C (Exact 3-Set Cover) and 3SAT—to Borda control problems, they prove that solving these election manipulations is as difficult as solving the underlying mathematical benchmarks.
Key technical components include:
- Preference Profile Construction: Designing specific sets of votes to create precise point spreads between candidates.
- Winner Models: Distinguishing between the unique-winner model (where the chair wants candidate $p$ to be the sole winner) and the nonunique-winner model (where $p$ being among the winners is sufficient).
- Tie-Handling Rules: Analyzing two distinct rules for sub-elections: "Ties-Eliminate" (TE), where only a unique winner advances, and "Ties-Promote" (TP), where all winners advance.
Key Results
The authors successfully classified 10 new cases, filling significant gaps in the literature. The findings reveal a clear divide between constructive and destructive efforts.
Constructive Resistance vs. Destructive Vulnerability
The research confirms that Borda is resistant (NP-hard) to every standard type of constructive control. If a chair seeks to make a specific candidate win by altering the election structure, no efficient algorithm exists to guarantee success. Conversely, Borda is vulnerable (solvable in polynomial time) to most forms of destructive control; it is mathematically simpler to ensure a candidate loses than to ensure they win.
The "Winner Model" Gap
A striking finding emerged in the case of "destructive control by partition of candidates" (DCPC-TP). The authors proved this case is easy (in P) in the nonunique-winner model but hard (NP-hard) in the unique-winner model. This is a rare occurrence in social choice theory, as the two winner models typically share the same complexity profile.
Discussion and Future Work
While this paper settles 10 cases, one final piece of the puzzle remains: the complexity of DCPC-TP in the unique-winner model. Future research may also explore parameterized complexity to see if these problems become tractable when certain variables, such as the number of candidates, are small. Additionally, the authors suggest investigating "online control," where decisions must be made as votes arrive sequentially, and seeking "dichotomy results" that could predict control complexity for all positional scoring rules beyond just Borda.
Summary updated