Source-linked AI summary
The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control
P. Faliszewski, E. Hemaspaandra, L. A. Hemaspaandra, J. Rothe
TL;DR
The paper asks whether complexity-based protections against electoral manipulation and control remain effective for electorates with canonical single-peaked preferences. It studies control and manipulation under this restriction and finds that many general-case NP-hardness results become polynomial-time solvable, although some hard cases remain. The authors therefore conclude that single-peaked preferences remove many complexity-theoretic shields, within the model’s scope.
Problem
The paper addresses whether NP-hardness protections against election control and manipulation survive when electorates follow the canonical single-peaked preference model.
Method
The paper analyzes election control and manipulation for single-peaked approval-vector and linear-order electorates, proving complexity classifications and introducing single-peaked approval voting.
Results
Many control and manipulation problems that are NP-hard in general have polynomial-time algorithms for single-peaked electorates, while some manipulation problems remain NP-hard.
Takeaways & Limitations
Single-peaked preferences remove many complexity-theoretic shields against electoral control and manipulation, but do not remove hardness in every case.
Takeaways & Limitations
Single-peakedness is an extreme unidimensional model that does not typically capture multidimensional issues and may exclude maverick voters focused on other issues.
Abstract
from arXiv · showhide
Much work has been devoted, during the past twenty years, to using complexity to protect elections from manipulation and control. Many results have been obtained showing NP-hardness shields, and recently there has been much focus on whether such worst-case hardness protections can be bypassed by frequently correct heuristics or by approximations. This paper takes a very different approach: We argue that when electorates follow the canonical political science model of societal preferences the complexity shield never existed in the first place. In particular, we show that for electorates having single-peaked preferences, many existing NP-hardness results on manipulation and control evaporate.
1 Introduction
The paper examines whether NP-hardness protections against electoral control and manipulation survive under single-peaked preferences, a canonical political-science model. It introduces single-peaked approval voting and shows that many general-case hardness results become polynomial-time solvable, while some manipulation problems remain hard.
- The paper introduces single-peakedness for approval-voting elections, where each voter’s approved candidates are contiguous in a societal candidate order.For linear orders, preferences increase, decrease, or increase then decrease along that order.
- Single-peaked electorates make many election control problems polynomial-time solvable, even when those problems are NP-hard for general electorates.The result applies to both approval-vector and linear-order voting.
- The paper likewise identifies many manipulation problems that become polynomial-time solvable under single-peaked preferences.This concerns both the approval and linear-order settings discussed by the paper.
- The paper also shows that single-peakedness does not eliminate hardness: many manipulation problems remain NP-hard in this restricted setting.This extends the paper’s analysis beyond cases where the complexity shield disappears.
- In 3-veto elections, manipulation is in P with up to four candidates, NP-hard with five, and in P again with six or more candidates.Thus, increasing the number of candidates can reduce complexity in the single-peaked case.
- The authors argue that standard voting rules remain relevant because real-life rules are typically fixed, even when the electorate is known to be single-peaked.They distinguish incentives to manipulate from the separate question of which voting rule is used.
2 Preliminaries
The paper models elections with approval vectors or linear orders and studies single-peaked preferences along a common candidate order. It introduces polynomial-time recognition for single-peaked approval profiles and formalizes control and manipulation problems under this setting.
- Election Systems: Approval voting selects candidates with the most approvals, while scoring protocols assign position-dependent scores according to a nonincreasing scoring vector.The paper also uses plurality, veto, and j-veto systems as scoring protocols.
- Single-Peaked Preferences: Single-peaked preferences require a common candidate order in which each voter’s linear-order preferences rise to a peak and then fall.For approval vectors, the analogous condition is that each voter’s approved candidates form a contiguous block.
- Scope of the Model: The single-peaked model is useful for unidimensional issues but excludes multidimensional settings and can miss voters focused on other issues.The authors therefore characterize it as a widely studied yet extreme model rather than a universally appropriate assumption.
- Recognizing Single-Peakedness: Given approval vectors, a polynomial-time algorithm can find a linear order witnessing single-peakedness or determine that none exists.This recognition result is specific to approval-vector profiles and does not follow directly by extending them into linear orders.
- Control and Manipulation: Control changes participation by adding or deleting voters or candidates, whereas manipulation lets a coalition strategically change its votes to affect a designated candidate’s outcome.The paper studies constructive control and weighted coalition manipulation across its election systems.
3 Control
Single-peaked electorates make many control problems tractable: restricting approval-vector and linear-order votes causes general-case NP-hardness reductions to fail. The section also identifies exceptions, including a contrived election system where single-peakedness increases manipulation complexity.
- 3 Control: Single-peakedness makes many control problems polynomial-time solvable, because its restricted vote collections undermine reductions establishing general-case NP-hardness.The paper frames this as the central reason complexity shields evaporate under single-peaked preferences.
- 3 Control: Approval voting is vulnerable to constructive control by adding or deleting voters in both winner models and both standard and succinct input models.
- 3 Control: The control algorithms use structured greedy or polynomial-time procedures that order interval votes and defeat dangerous rivals while preserving any possible route to success.The adding-candidates proof groups votes by interval endpoints and then re-sorts them; the proof proceeds rival by rival using a safest path.
- 3 Control: Plurality is vulnerable to constructive and destructive control by adding or deleting candidates in both unique-winner and nonunique-winner models.The stated candidate-control results include adding candidates, unlimited candidate addition, and candidate deletion.
- 3 Control: For plurality and approval, every adding/deleting case known to have an NP-hardness shield becomes vulnerable for single-peaked societies, although some manipulation shields remain.
- 3 Control: The tractability pattern is not universal: a highly artificial approval-based election system has polynomial-time general manipulation but NP-complete size-3-coalition manipulation under single-peakedness.The hardness proof reduces Boolean satisfiability and relies on the restricted single-peaked model.
4 Manipulation
Under single-peaked preferences, many manipulation problems that are NP-hard in general become polynomial-time solvable, although hardness persists for selected election systems and candidate counts.
- The tractable cases exploit the restricted single-peaked vote orders, allowing the algorithm to test a small set of strategically relevant manipulation actions.
- The results show that single-peakedness removes many general-case NP-hardness shields, while some manipulation problems remain resistant under the restriction.
- Single-peaked manipulation is in P for the systems covered by Theorem 4.1, including 3-candidate Borda elections and several approval/veto-related protocols.
- For m-candidate 3-veto elections, manipulation is in P for m ∈{3, 4, 6, 7, 8, . . .} but NP-complete for m = 5.
- For three-candidate scoring protocols, manipulation is NP-complete when α1 −α3 > 2(α2 −α3) > 0 and is in P otherwise.
5 Related Work
The paper builds on prior work showing both efficient reasoning about single-peaked preferences and manipulation hardness that survives single-peakedness. Its emphasis differs by showing that many general-case complexity shields disappear on single-peaked domains.
- Walsh showed that weighted manipulation for single transferable vote remains NP-hard in single-peaked societies, preserving an NP-completeness shield.
- Earlier work provides efficient algorithms for testing single-peakedness and producing a valid societal candidate ordering for linear-order votes.
- Conitzer studied how single-peaked preferences can be elicited quickly through pairwise comparison queries, with and without a known societal ordering.
- Political-science research has characterized single-peakedness and examined its implications for scoring protocols, Condorcet-type criteria, and Arrow’s Theorem.
6 Conclusions and Future Directions
The paper concludes that single-peaked preferences eliminate many complexity-theoretic shields against election control and manipulation, so unrestricted-model results cannot be assumed to apply. It identifies open questions about dichotomies, multidimensional preferences, and societies that are nearly single-peaked.
- Conclusion: Single-peaked preferences remove many complexity-theoretic shields against control and manipulation, which may invalidate conclusions drawn from unrestricted preference models.The paper argues that these shields did not exist for single-peaked electorates and cautions against relying on unrestricted-model results.
- Future Directions: A dichotomy theorem for manipulating scoring protocols remains an open goal beyond the three-candidate case resolved by Theorem 4.4.The general, unrestricted model has a complete dichotomy, while the single-peaked setting has only partial results in this discussion.
- Future Directions: The paper leaves open whether shield removals extend from unidimensional single-peaked preferences to appropriate two-dimensional or k-dimensional analogues.Throughout the paper, single-peakedness is defined only in the unidimensional case.
- Future Directions: It also asks whether the shield-evaporation results extend to societies that are very nearly, rather than exactly, single-peaked.The motivation is that real societies may contain voters whose preferences are shaped by issues outside the dominant dimension.
- Related Work: Subsequent work further examined bribery and control by partition of voters and generalized Theorem 4.4 to each fixed number of candidates.These developments are attributed to Brandt et al.