Abstract
In the field of computational social choice, the complexity of manipulating election outcomes is a central concern. This paper establishes the first complete complexity-theoretic classification—a dichotomy theorem—for the problem of Constructive Control by Adding Voters (CCAV) within the class of pure scoring rules. We identify exactly four categories of scoring rules where this form of election control is computationally tractable (P), and prove that for all other pure scoring rules, the problem is NP-complete. This work clarifies the boundary between security and vulnerability in voting systems, highlighting how the mathematical structure of scoring coefficients dictates computational hardness.
Introduction
Election control refers to the efforts of an external agent, often called the "chair," to alter the outcome of an election through strategic structural changes. One of the most studied variants is Constructive Control by Adding Voters (CCAV), where the chair attempts to ensure a preferred candidate wins by recruiting a subset of potential voters from a provided pool, subject to a budget constraint $k$.
While previous literature has analyzed specific rules like Plurality or Borda Count, a unified understanding of the entire family of pure scoring rules remained elusive. A scoring rule assigns points to candidates based on their rank in a voter's preference list. A rule is considered "pure" if the scoring vectors for different numbers of candidates are generated consistently (e.g., by inserting a new coefficient into the existing sequence as the candidate pool grows). This paper provides a definitive map for this infinite family of rules.
Defining the Pure Scoring Rule
A scoring rule is defined by a vector $(\alpha_1, \alpha_2, \dots, \alpha_m)$ where $\alpha_1 \ge \alpha_2 \ge \dots \ge \alpha_m$. In a pure scoring rule, these vectors are not independent; they must follow a consistent generation logic as $m$ increases. The authors demonstrate that this "purity" constraint is mathematically significant. For instance, allowing rational numbers for coefficients enables a broader range of pure rules than using only integers—a distinction that is irrelevant in non-pure settings. Furthermore, the paper establishes a "hierarchy theorem," showing that the variety of representable voting systems increases with the computational time allowed to generate the scoring coefficients.
The Control Dichotomy
The core contribution of this research is the Control Dichotomy Theorem. It asserts that CCAV is solvable in polynomial time if and only if the pure scoring rule is equivalent to one of the following four types:
- $k$-approval for $k \le 3$: Voters assign 1 point to each of their top $k$ candidates and 0 to others.
- $k$-veto for $k \le 2$: Voters assign 1 point to all candidates except their bottom $k$, who receive 0.
- Top-Two Rules: Any rule where only the first and second-ranked candidates receive non-zero scores (e.g., $(2, 1, 0, \dots, 0)$).
- The (2, 1, ..., 1, 0) Hybrid: A specific rule where the top candidate receives 2 points, the bottom candidate receives 0, and all intermediate candidates receive 1 point.
For every other possible pure scoring rule, the CCAV problem is proven to be NP-complete. This result provides a clear boundary for the computational security of elections against voter addition.
Methodology
The authors utilized a dual-track approach to establish this dichotomy:
Algorithm Design for Tractability
For the four "easy" cases, the authors developed polynomial-time algorithms. These solutions often rely on greedy strategies or reductions to min-cost network flow problems, where the task of selecting the optimal subset of voters is modeled as finding an optimal flow through a directed graph.
Complexity Reductions for Hardness
To prove NP-completeness for all other rules, the authors employed sophisticated reductions from the 3-Dimensional Matching (3DM) problem. A key challenge was showing how the fixed coefficients of a scoring rule could be used to "simulate" the behavior of $k$-veto or $k$-approval rules within the reduction gadget.
One of the most surprising findings was the sensitivity of the "hybrid" rule. In most systems, complexity depends on the relative order of scores. However, in the $(2, 1, \dots, 1, 0)$ case, the specific values matter: changing the top score from 2 to 3 shifts the problem from P to NP-complete.
Discussion and Future Work
This classification provides a rigorous foundation for understanding election control, yet several avenues for expansion remain. The current model assumes unweighted voters; in scenarios where voters have different weights (such as shareholder meetings), the control problem typically becomes harder. Additionally, while this paper focuses on adding voters, the boundaries for other control types—such as deleting voters or adding/removing candidates—may follow different patterns. Finally, while the "pure" constraint captures most standard voting systems, generalizing these results to non-pure or "flexible" scoring rules remains a significant open challenge in computational social choice.
Summary updated