Parameterized Computational Complexity of Dodgson and Young Elections

DOI10.1007/978-3-540-69903-3_36zbMath1155.91340OpenAlexW1688326505MaRDI QIDQ3512476

Nadja Betzler, Jiong Guo, Rolf Niedermeier

Publication date: 15 July 2008

Published in: Algorithm Theory – SWAT 2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69903-3_36

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ Fixed-parameter algorithms for Kemeny rankings ⋮ Parameterized complexity of candidate control in elections and related digraph problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dichotomy for voting systems
• Approximability of Dodgson's rule
• Voting schemes for which it can be difficult to tell who won the election
• Extending Condorcet's rule
• Exact complexity of the winner problem for Young elections
• On complexity of lobbying in multiple referenda
• Parametrized complexity theory.
• Fixed-Parameter Algorithms for Kemeny Scores
• When are elections with few candidates hard to manipulate?
• Exact analysis of Dodgson elections
• A Short Introduction to Computational Social Choice
• Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners

This page was built for publication: Parameterized Computational Complexity of Dodgson and Young Elections