Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control

Gábor Erdélyi, Markus Nowak, Jörg Rothe

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:

  1. Preference Rankings: Voters rank candidates from most to least preferred.
  2. 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.
Comparison of computational resistance across various voting systems.

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

Abstract

We study sincere-strategy preference-based approval voting (SP-AV), a system proposed by Brams and Sanver [Electoral Studies, 25(2):287-305, 2006], and here adjusted so as to coerce admissibility of the votes (rather than excluding inadmissible votes a priori), with respect to procedural control. In such control scenarios, an external agent seeks to change the outcome of an election via actions such as adding/deleting/partitioning either candidates or voters. SP-AV combines the voters' preference rankings with their approvals of candidates, where in elections with at least two candidates the voters' approval strategies are adjusted--if needed--to approve of their most-preferred candidate and to disapprove of their least-preferred candidate. This rule coerces admissibility of the votes even in the presence of control actions, and hybridizes, in effect, approval with pluralitiy voting. We prove that this system is computationally resistant (i.e., the corresponding control problems are NP-hard) to 19 out of 22 types of constructive and destructive control. Thus, SP-AV has more resistances to control than is currently known for any other natural voting system with a polynomial-time winner problem. In particular, SP-AV is (after Copeland voting, see Faliszewski et al. [AAIM-2008, Springer LNCS 5034, pp. 165-176, 2008]) the second natural voting system with an easy winner-determination procedure that is known to have full resistance to constructive control, and unlike Copeland voting it in addition displays broad resistance to destructive control.
BibTeX
@article{erdelyi2009sincere,
  author = {Gábor Erdélyi and Markus Nowak and Jörg Rothe},
  title = {{Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control}},
  journal = {Math. Log. Q.},
  year = {2009},
  doi = {10.1002/malq.200810020},
}
Figure