The complexity of Kemeny elections
From MaRDI portal
Publication:817813
DOI10.1016/j.tcs.2005.08.031zbMath1086.68046OpenAlexW2057573268MaRDI 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
Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (50)
More results on the complexity of identifying problems in graphs ⋮ Isomorphic Distances Among Elections ⋮ Guarantees for the success frequency of an algorithm for finding Dodgson-election winners ⋮ Manipulation complexity of same-system runoff elections ⋮ The complexity of priced control in elections ⋮ Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games ⋮ Studies in Computational Aspects of Voting ⋮ Dichotomy for voting systems ⋮ The Network HHD: Quantifying Cyclic Competition in Trait-Performance Models of Tournaments ⋮ The complexity of probabilistic lobbying ⋮ A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison ⋮ The complexity of computing minimal unidirectional covering sets ⋮ A unifying rank aggregation framework to suitably and efficiently aggregate any kind of rankings ⋮ On weakly and strongly popular rankings ⋮ Recognizing when a preference system is close to admitting a master list ⋮ The possible winner with uncertain weights problem ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Fixed-Parameter Algorithms for Kemeny Scores ⋮ Beyond the worst case: semi-random complexity analysis of winner determination ⋮ Computing kemeny rankings from \(d\)-Euclidean preferences ⋮ Unnamed Item ⋮ On the computation of median linear orders, of median complete preorders and of median weak orders ⋮ Unnamed Item ⋮ Manipulation can be hard in tractable voting systems even for constant-sized coalitions ⋮ The Complexity Landscape of Outcome Determination in Judgment Aggregation ⋮ Using extension sets to aggregate partial rankings in a flexible setting ⋮ Voting Procedures, Complexity of ⋮ On complexity of lobbying in multiple referenda ⋮ Complexity of stability ⋮ Predicting winner and estimating margin of victory in elections using sampling ⋮ Graph aggregation ⋮ Complexity of Stability. ⋮ Robustness among multiwinner voting rules ⋮ An updated survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Average parameterization and partial kernelization for computing medians ⋮ Approaching rank aggregation problems by using evolution strategies: the case of the optimal bucket order problem ⋮ Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP ⋮ Hybrid Elections Broaden Complexity-Theoretic Resistance to Control ⋮ The Computational Complexity of Choice Sets ⋮ Finding Optimal Solutions With Neighborly Help. ⋮ An Algorithmic View of Voting ⋮ Packing Arc-Disjoint Cycles in Tournaments ⋮ Anyone but him: the complexity of precluding an alternative ⋮ Aggregation over Metric Spaces: Proposing and Voting in Elections, Budgeting, and Legislation ⋮ Fixed-parameter algorithms for Kemeny rankings ⋮ Preservation of semantic properties in collective argumentation: the case of aggregating abstract argumentation frameworks ⋮ COMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCES ⋮ Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner ⋮ Complexity results for extensions of median orders to different types of remoteness ⋮ Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results
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
This page was built for publication: The complexity of Kemeny elections
