Manipulation complexity of same-system runoff elections

DOI10.1007/S10472-015-9490-6MaRDI QIDQ314418zbMATH OpenOpenAlexFDO

Authors Zack Fitzsimmons, Edith Hemaspaandra, Lane A. Hemaspaandra

Publication date 16 September 2016

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.6118

zbMATH Keywords

votingsocial choicerunoff elections

Mathematics Subject Classification ID

Group preferences (91B10) Social choice (91B14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12)

Abstract: Do runoff elections, using the same voting rule as the initial election but just on the winning candidates, increase or decrease the complexity of manipulation? Does allowing revoting in the runoff increase or decrease the complexity relative to just having a runoff without revoting? For both weighted and unweighted voting, we show that even for election systems with simple winner problems the complexity of manipulation, manipulation with runoffs, and manipulation with revoting runoffs are independent, in the abstract. On the other hand, for some important, well-known election systems we determine what holds for each of these cases. For no such systems do we find runoffs lowering complexity, and for some we find that runoffs raise complexity. Ours is the first paper to show that for natural, unweighted election systems, runoffs can increase the manipulation complexity.

Recommendations

• When are elections with few candidates hard to manipulate?
• Where are the hard manipulation problems?
• Election Manipulation 100
• Complexity of manipulative actions when voting with ties
• The computational difficulty of manipulating an election

Cites work

• scientific article; zbMATH DE number 6747925 (Why is no real title available?)
• A Richer Understanding of the Complexity of Election Systems
• A Short Introduction to Computational Social Choice
• Algorithms and Computation
• Algorithms for the coalitional manipulation problem
• Anyone but him: the complexity of precluding an alternative
• Barriers to manipulation in voting
• Best reply dynamics for scoring rules
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Competing provers yield improved Karp-Lipton collapse results
• Dichotomy for voting systems
• Exact analysis of Dodgson elections
• Exact complexity of the winner problem for Young elections
• Manipulation complexity of same-system runoff elections
• Multi-stage voting, sequential elimination and Condorcet consistency
• Multiagent Systems
• Search versus decision for election manipulation problems
• Single transferable vote resists strategic voting
• The complexity of Kemeny elections
• The computational difficulty of manipulating an election
• Voting schemes for which it can be difficult to tell who won the election
• Weighted manipulation for four-candidate Llull is easy
• When are elections with few candidates hard to manipulate?
• Where are the hard manipulation problems?

Cited in

(4)

• The complexity of online bribery in sequential elections
• Manipulation complexity of same-system runoff elections
• The computational difficulty of manipulating an election
• Combining voting rules together

This page was built for publication: Manipulation complexity of same-system runoff elections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q314418)