Abstract
We study Sincere-Strategy Preference-Based Approval Voting (SP-AV), a hybrid voting system that combines preference rankings with approval sets. By implementing a strategy rewrite rule that coerces vote admissibility, SP-AV achieves unprecedented computational resistance to procedural control. Our analysis proves that SP-AV is NP-hard to manipulate in 19 out of 22 standard control scenarios, making it one of the most robust "natural" voting systems identified to date.
Introduction: The Challenge of Electoral Control
In the field of Computational Social Choice, researchers seek voting systems that are not only fair but also mathematically difficult to manipulate. One common form of manipulation is procedural control, where an external authority (the "chair") attempts to influence the outcome by altering the structure of the election—such as by adding, deleting, or partitioning candidates and voters.
While most voting systems are theoretically susceptible to these tactics, the goal is to find systems where finding a successful manipulation strategy is NP-hard. If a problem is NP-hard, it is computationally infeasible for a chair to find a perfect "rigging" strategy in a large-scale election. This paper explores SP-AV as a solution that offers broad resistance to both constructive control (trying to make a favorite win) and destructive control (trying to make a candidate lose).
The SP-AV Mechanism and the Admissibility Rule
SP-AV, originally proposed by Brams and Sanver, integrates two distinct voting methods:
- Preference Rankings: Voters rank candidates from most to least preferred.
- Approval Sets: Voters designate which candidates they "approve" of and which they "disapprove."
A key innovation in this study is the AV Strategy Rewrite Rule. In many control scenarios, structural changes (like deleting candidates) can leave a voter's strategy "inadmissible" (e.g., approving of everyone or no one). This rule automatically adjusts such votes to ensure every voter approves of at least their top-ranked candidate and disapproves of at least their bottom-ranked candidate. This coercion of admissibility prevents the system from collapsing into triviality during structural manipulation.
Methodology: Proving Computational Resistance
To establish the difficulty of manipulating SP-AV, the authors utilize polynomial-time reductions. They demonstrate that if a chair could efficiently solve the control problem for SP-AV, they could also solve classic NP-complete problems such as Hitting Set and Exact Cover by Three-Sets (X3C). This theoretical framework proves that SP-AV's resistance is a fundamental mathematical barrier rather than a mere design quirk.
Key Results and Comparative Analysis
The study evaluated 22 types of electoral control. SP-AV demonstrated remarkable robustness compared to other common voting systems:
- Full Constructive Resistance: SP-AV is only the second "natural" system (after Copeland voting) shown to be resistant to all 11 types of constructive control.
- Broad Destructive Resistance: Unlike Copeland voting, which is easily manipulated destructively, SP-AV remains resistant to 8 out of 11 types of destructive control.
As shown in the table above, SP-AV significantly outperforms traditional systems like Condorcet, Approval, and Plurality. By breaking properties like "Unique-WARP" (consistency between large groups and subgroups), SP-AV introduces a level of complexity that thwarts strategic manipulation across nearly all candidate-based control scenarios.
Conclusion
SP-AV represents a significant advancement in the design of secure voting mechanisms. By hybridizing preference and approval data and enforcing vote admissibility, it creates a system that is easy for voters to use but mathematically daunting for manipulators. While NP-hardness focuses on worst-case scenarios, the broad resistance of SP-AV across 19 different control types suggests it is a highly viable candidate for robust, manipulation-resistant democratic processes.
Summary updated