Guarantees for the success frequency of an algorithm for finding Dodgson-election winners

DOI10.1007/s10732-007-9068-5zbMath1188.91062OpenAlexW1516798378MaRDI QIDQ835761

Christopher M. Homan, Hemaspaandra, Lane A.

Publication date: 31 August 2009

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://scholarworks.rit.edu/cgi/viewcontent.cgi?article=1683&context=article

zbMATH Keywords

computational social choiceDodgson electionsfrequently self-knowingly correct heuristicsLewis Carroll

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Voting theory (91B12) Social choice (91B14)

Related Items (12)

The complexity of online bribery in sequential elections ⋮ Generalized juntas and NP-hard sets ⋮ Beyond the worst case: semi-random complexity analysis of winner determination ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ Proportional Approval Voting, Harmonic k-median, and Negative Association ⋮ On the approximability of Dodgson and Young elections ⋮ Parameterized computational complexity of Dodgson and Young elections ⋮ Hybrid Elections Broaden Complexity-Theoretic Resistance to Control ⋮ Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control ⋮ Approximability of Dodgson's rule ⋮ Computational Aspects of Approval Voting ⋮ Socially desirable approximations for dodgson’s voting rule

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independence of clones as a criterion for voting rules
• The strong exponential hierarchy collapses
• Approximate solution of NP optimization problems
• The complexity of Kemeny elections
• 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
• Exact complexity of the winner problem for Young elections
• Integer Programming with a Fixed Number of Variables
• Bounded Query Classes
• Smoothed analysis of algorithms
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• How Hard Is Bribery in Elections?
• Average Case Complete Problems
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The Boolean Hierarchy I: Structural Properties
• Canonical Coin Changing and Greedy Solutions
• Exact analysis of Dodgson elections
• A Tight Analysis of the Greedy Algorithm for Set Cover
• On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time
• Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners
• On Worst‐Case to Average‐Case Reductions for NP Problems
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Guarantees for the success frequency of an algorithm for finding Dodgson-election winners