Source-linked AI summary
How Hard Is It to Control an Election by Breaking Ties?
Nicholas Mattei, Nina Narodytska, Toby Walsh
TL;DR
The paper asks how difficult it is for an election chair to control outcomes by strategically breaking ties, a problem equivalent to winner determination under parallel universes tie-breaking. It formalizes tie-breaking control and analyzes voting rules and tie-breaking functions. The main result is that control is easy when selecting among final co-winners but can be NP-complete in multi-round and even two-stage elections.
Problem
The paper studies whether strategically choosing tie-breaks creates a computational barrier to election control, including when the chair knows how votes were cast.
Method
The paper formalizes tie-breaking as a single-valued choice function and analyzes control across voting correspondences, multi-round rules, and tie-breaking settings.
Results
Control is polynomial when the chair only selects among co-winners, but can be NP-complete for multi-round rules and even two-stage rules.
Takeaways & Limitations
The form and repeated use of tie-breaking can substantially increase opportunities for election control, and tie-breaking control need not match manipulation complexity.
Takeaways & Limitations
The results are worst-case and may not reflect the practical or average-case difficulty of manipulation.
Abstract
from arXiv · showhide
We study the computational complexity of controlling the result of an election by breaking ties strategically. This problem is equivalent to the problem of deciding the winner of an election under parallel universes tie-breaking. When the chair of the election is only asked to break ties to choose between one of the co-winners, the problem is trivially easy. However, in multi-round elections, we prove that it can be NP-hard for the chair to compute how to break ties to ensure a given result. Additionally, we show that the form of the tie-breaking function can increase the opportunities for control. Indeed, we prove that it can be NP-hard to control an election by breaking ties even with a two-stage voting rule.
1 INTRODUCTION
The paper frames tie-breaking as an underexamined form of election control and connects it to parallel universes tie-breaking. It shows that control is easy when choosing among final co-winners but can be NP-complete in multi-round and even two-stage elections.
- Tie-breaking control is motivated by the chair’s ability to select a beneficial outcome when tie rules are unspecified or ambiguous.
- Control by tie-breaking is equivalent to deciding whether a preferred candidate can win under some tie-breaking rule, known as parallel universes tie-breaking.
- PUT restores neutrality because it considers all tie-breaking rules rather than privileging candidate names through a fixed ordering.
- When the chair chooses only among co-winners, control is polynomial; for many multi-round rules, it is NP-complete.The multi-round examples include Coombs, Cup, and STV.
- Even two-stage voting rules can make control by tie-breaking NP-complete, despite requiring at most two tie decisions.
2 FORMAL BACKGROUND
The paper formalizes elections, voting correspondences, tie-breaking functions, and the decision problem of making a preferred candidate the unique winner. It introduces the voting rules used to analyze when tie-breaking control is vulnerable or resistant.
- An election consists of candidates, strict voter rankings, and a voting correspondence that returns a set of co-winners.A tie-breaking rule selects one candidate when the correspondence returns multiple co-winners.
- The study covers scoring, runoff, elimination, pairwise, and ranking-based rules, including plurality, Borda, STV, Coombs, Copelandα, Schulze, and Kemeny-Young.The supplied passages define representative procedures within these rule families.
- A tie-breaking rule is a single-valued choice function that selects one candidate from any nonempty winner set for a given profile.The definition permits nontransitive functions, including sports-style rules based on statistics.
- The control problem asks whether some tie-breaking rule can make a preferred candidate p the election’s unique winner.
- A rule is vulnerable to tie-breaking control when the problem is polynomial and resistant when it is NP-hard.
3 RELATIONSHIP TO MANIPULATION
The paper shows that tie-breaking control and manipulation complexity need not coincide. It gives voting correspondences where one problem is polynomial while the other is NP-complete, in both random-tie and standard manipulation settings.
- Tie-breaking control is computationally unrelated to manipulation with random tie-breaking or a fixed tie-breaking order.
- There exists a voting correspondence where tie-breaking control is polynomial but random-tie manipulation is NP-complete, and vice versa.
- For a rule that first eliminates half the candidates by veto and then elects the plurality winner, tie-breaking control is NP-complete while random-tie manipulation is polynomial.
- There exists a voting correspondence where tie-breaking control is polynomial but manipulation is NP-complete, and vice versa.
- The same veto-then-plurality rule has NP-complete tie-breaking control but polynomial standard manipulation.
4 SELECTING FROM THE WINNING SET
The section distinguishes easy control from harder cases by examining how many times ties are resolved and how tie-breaking choices affect later rounds. It proves polynomial cases for final co-winner selection and for several listed rules, while multi-round rules can be resistant.
- If tie-breaking occurs once at the end among co-winners, control is polynomial and p can win exactly when p is a co-winner.
- Polynomial control holds for all scoring rules, Bucklin, Black, maximin, and Copelandα for every α.
- Plurality with runoff is polynomial because only O(m) candidates can enter a runoff with the preferred candidate, allowing all possibilities to be tried.
- Nanson remains polynomial for tie-breaking control despite NP-complete manipulation, because ties arise only in its final round.
- Multi-round rules such as STV and Coombs create more control opportunities because candidates are successively eliminated and ties may recur.
- Setting Copelandα’s tie score α is itself a polynomial control problem.
5 BREAKING TIES DURING EXECUTION
For multi-round voting rules, strategically choosing which tied candidate to eliminate can encode hard combinatorial choices. The paper proves NP-completeness for Baldwin and Coombs, while Cup and Copeland show complexity changes depending on tournament structure and tie-breaking transitivity.
- Baldwin and Coombs rules: NP-completeness holds for control by tie-breaking under Baldwin’s rule.Baldwin successively eliminates candidates using Borda scores; the construction transfers the burden of finding an exact cover from manipulation to tie-breaking.
- Baldwin and Coombs rules: The Baldwin construction uses tied candidates and score-controlled eliminations to make the preferred candidate win exactly when selected sets form an exact cover.Candidates corresponding to sets are eliminated through successive tied rounds, and the preferred candidate can then defeat the remaining candidates if and only if the cover was selected.
- Baldwin and Coombs rules: NP-completeness also holds for control by tie-breaking under Coombs’s rule.The reduction modifies initial veto scores so that tie-breaking, rather than a manipulator’s vote, selects the required cover and determines subsequent eliminations.
- Cup and Copeland: For Cup, control is polynomial when each candidate appears only once in the schedule.An algorithm for computing a manipulating vote supplies a linear tie-breaking order, and non-transitive tie-breaking cannot help when candidates have only one appearance.
- Cup and Copeland: For arbitrary Cup schedules with repeated candidate appearances, control by tie-breaking becomes NP-complete.The hardness proof reduces from 3SAT, using pairwise tie-breaking choices to select literals that satisfy every clause.
- Cup and Copeland: For Copeland, control remains polynomial when pairwise ties may be resolved by a non-transitive ordering.Non-transitive pairwise tie-breaking can increase control opportunities, but the resulting Copeland control problem is nevertheless polynomial.
6 COMBINING VOTING RULES
Combining voting rules can make control by tie-breaking computationally hard, even when only a small number of tie-breaks occur. However, some hybrid rules become polynomial-time controllable when the number of rounds or surviving candidates is bounded.
- Two-stage rules: A two-stage voting rule based on veto followed by plurality has NP-complete control by tie-breaking.The first stage eliminates candidates using veto, and tie-breaking selects the subset entering the plurality runoff.
- Two-stage rules: Control by tie-breaking is NP-complete for Cup1 + Plurality, Cup1 + Borda, and Cup1 + Maximin.The reductions use tied first-round literal pairs, allowing tie-breaking choices to simulate a satisfying assignment.
- Hybrid rules: HYB(Pluralityk,Plurality) has polynomial-time control when k or m−k is bounded.One can enumerate O(m^k) elimination decisions when k is bounded, or O(m^(m−k)) survival decisions when m−k is bounded.
- Hybrid rules: When k is unbounded, control by tie-breaking for HYB(Pluralityk,Plurality) is NP-complete.The hardness reduction is from X3C and encodes items and sets as election candidates.
- Hybrid rules: In the X3C construction, tie-breaking must leave a set cover among the surviving set candidates for the preferred candidate to win.If the survivors fail to cover an item, that item candidate gains enough plurality points to defeat the preferred candidate.
7 CONCLUSION
The paper identifies the complexity of controlling elections through strategic tie-breaking and relates it to parallel universes tie-breaking. Its results range from trivial polynomial cases to NP-completeness in multi-round and two-stage elections, while the practical prevalence of these worst-case difficulties remains open.
- Conclusion: Control by tie-breaking is equivalent to deciding whether an election winner exists under parallel universes tie-breaking.Choosing among co-winners is trivially polynomial, but multiple tie-breaking decisions can make control NP-complete.
- Conclusion: The form of the tie-breaking function can increase opportunities for control.The paper summarizes these complexity results in Table 1, including results for ranked pairs and STV from prior work.
- Conclusion: Even with a two-stage voting rule and at most two tie-breaks, control by tie-breaking can be NP-hard.This result shows that hardness does not require a large number of sequential tie-breaking opportunities.
- Conclusion: Many results are worst-case and may not reflect the practical difficulty of manipulation.The authors plan to study hardness using PrefLib and other data sources.