TL;DR
This paper introduces and analyzes "Sincere-Strategy Preference-Based Approval Voting" (SP-AV), a novel voting system designed to be highly resistant to manipulation by external agents (the "chair"). SP-AV achieves remarkable resilience against 19 out of 22 common control scenarios, outperforming existing natural voting systems in its robustness.
What Problem Does This Paper Address?
In democratic and computational settings, voting systems are susceptible to manipulation. An external agent, often called a "chair," can try to influence election outcomes by altering the election's structure. This can involve adding or removing candidates or voters, or partitioning them. The challenge is to design voting systems that are computationally difficult to manipulate, even for an agent with complete knowledge of voter preferences. While systems like approval voting and plurality have been studied extensively for their resistance to such "control" actions, they still have vulnerabilities. This paper aims to create a system that combines the strengths of preference-based and approval voting to achieve a higher level of control resistance.
Methods
The authors introduce SP-AV, a system that combines voters' preference rankings with their approval of candidates. A key innovation is a rule that "coerces admissibility" of votes, ensuring that even if control actions make a vote technically inadmissible, it's automatically adjusted to be valid. This rule is crucial for maintaining the system's integrity under manipulation. The core of the paper involves a rigorous complexity-theoretic analysis of SP-AV's resistance to 22 types of constructive (making a specific candidate win) and destructive (preventing a specific candidate from winning) control. This analysis relies on reducing these control problems to known NP-hard problems, such as the "Hitting Set" problem.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Coerced Admissibility is Key: The SP-AV system's ability to automatically adjust votes to be admissible, rather than simply discarding them, is a critical feature that allows it to maintain control resistance even when manipulation attempts would otherwise invalidate votes.
- Synergy of Preference and Approval: SP-AV effectively blends the strengths of preference-based voting (like plurality) and approval voting, leading to a system that inherits the control resistances of both.
- Beyond Immunity: Resistance is Powerful: While some systems are "immune" to certain controls (meaning manipulation is impossible), SP-AV achieves "resistance" (meaning manipulation is computationally hard). This is a significant achievement, as true immunity is rare for natural voting systems.
- SP-AV as a New Benchmark: The paper establishes SP-AV as a new standard for control resistance among natural voting systems with efficient winner determination.
Key Results
- SP-AV is resistant to 19 out of 22 types of constructive and destructive control.
- It is vulnerable to only 3 types of control.
- This makes SP-AV more resistant to control than any other known natural voting system with a polynomial-time winner problem.
- SP-AV is fully resistant to constructive control, similar to Copeland voting, but also broadly resistant to destructive control.
- It is fully resistant to candidate control, like plurality, but also broadly resistant to voter control.
- SP-AV does not satisfy the "Unique-WARP" property, which is a characteristic of some other voting systems and is relevant to their control properties.
Limitations and Future Work
- No Immunities: While SP-AV is highly resistant, it is not immune to any of the control types studied. This means that while manipulation is computationally hard, it's not strictly impossible. The authors suggest that the choice between SP-AV and systems with immunities (like approval voting for certain controls) depends on which types of control are considered most critical.
- Future Research: The authors propose expanding the study of SP-AV to include other computational properties beyond procedural control, such as its social choice properties. They also suggest exploring "typical-case complexity" models, moving beyond worst-case analysis.
Summary updated