The complexity of Kemeny elections

DOI10.1016/j.tcs.2005.08.031zbMath1086.68046MaRDI QIDQ817813

Edith Hemaspaandra, Holger Spakowski, Jörg Vogel

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.08.031

zbMATH Keywords

computational complexity; election systems; parallel access to NP

Mathematics Subject Classification ID

91B12: Voting theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Dichotomy for voting systems, On complexity of lobbying in multiple referenda, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, Fixed-Parameter Algorithms for Kemeny Scores

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
• The strong exponential hierarchy collapses
• More complicated questions about maxima and minima, and some closures of NP
• Voting schemes for which it can be difficult to tell who won the election
• A comparison of polynomial time reducibilities
• Exact complexity of the winner problem for Young elections
• Bounded Query Classes
• A Consistent Extension of Condorcet’s Election Principle
• Exact analysis of Dodgson elections
• Reducibility among Combinatorial Problems