Abstract
Computational complexity of voting manipulation is one of the most actively studied topics in the area of computational social choice, starting with the groundbreaking work of [Bartholdi et al., 1989]. Most of the existing work in this area, including that of [Bartholdi et al., 1989], implicitly assumes that whenever several candidates receive the top score with respect to the given voting rule, the resulting tie is broken according to a lexicographic ordering over the candidates. However, till recently, an equally appealing method of tie-breaking, namely, selecting the winner uniformly at random among all tied candidates, has not been considered in the computational social choice literature. The first paper to analyze the complexity of voting manipulation under randomized tiebreaking is [Obraztsova et al., 2011], where the authors provide polynomial-time algorithms for this problem under scoring rules and--under an additional assumption on the manipulator's utilities-- for Maximin. In this paper, we extend the results of [Obraztsova et al., 2011] by showing that finding an optimal vote under randomized tie-breaking is computationally hard for Copeland and Maximin (with general utilities), as well as for STV and Ranked Pairs, but easy for the Bucklin rule and Plurality with Runoff.
Introduction
In social choice theory, the Gibbard–Satterthwaite theorem establishes that any non-dictatorial voting rule with at least three candidates is susceptible to strategic manipulation. To mitigate this, researchers have turned to computational complexity as a barrier: if finding a manipulative vote is NP-hard, the rule may be considered practically resistant to manipulation.
Historically, most complexity analyses assumed lexicographic tie-breaking (e.g., breaking ties based on a fixed alphabetical order). However, many real-world systems employ randomized tie-breaking, where a winner is chosen uniformly at random from the set of tied candidates. This shift fundamentally changes the manipulator's objective from making a specific candidate win to maximizing their expected utility across all potential winners. This paper explores whether randomized tie-breaking alters the computational landscape of voting manipulation across several common voting rules.
Methodology
The study employs standard computational complexity analysis to classify various voting rules. To establish hardness, the authors use polynomial-time reductions from known NP-hard problems:
- Maximin (General Utilities): Reduced from the Feedback Vertex Set problem.
- Copeland: Reduced from the Independent Set problem.
- STV and Ranked Pairs: Derived from existing proofs regarding the complexity of becoming a "co-winner."
Conversely, to demonstrate that a rule is easy to manipulate (in class P), the authors provide constructive polynomial-time algorithms. For instance, for the Bucklin rule, they developed an algorithm that efficiently iterates through possible winning rounds to identify the utility-maximizing vote.
Key Insights
A central finding is that the complexity of manipulation is highly sensitive to the manipulator's utility function. While previous work suggested Maximin was easy to manipulate when the voter only cared about a single candidate (restricted utilities), this paper proves that the problem becomes NP-hard when the manipulator has a full ranking of preferences (general utilities).
Furthermore, the "lottery" aspect of randomized tie-breaking introduces a probabilistic layer that complicates the decision-making process for rules like Copeland. Manipulators must account for the likelihood of different candidates entering a tie, a calculation that often pushes the problem into the realm of NP-hardness.
Results
The research provides a comprehensive classification of common voting rules under the randomized tie-breaking paradigm. The results are summarized in the table below:
Rules classified as P (Scoring rules, Bucklin, Plurality with Runoff) are computationally vulnerable to individual manipulation. In contrast, rules classified as NP-hard (Copeland, Maximin with general utilities, STV, Ranked Pairs) offer a degree of computational protection against strategic voting.
Conclusion and Future Work
This work completes a significant portion of the "complexity map" for randomized tie-breaking. Future research directions include investigating coalitional manipulation, where groups of voters coordinate their actions, and exploring non-uniform randomized tie-breaking mechanisms. Additionally, the hardness results for Maximin and Copeland suggest a need for research into approximation algorithms that might find "near-optimal" manipulative votes efficiently.
Summary updated