Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners

2005/09/19 by Christopher M. Homan, Homan, Christopher M., Lane A. Hemaspaandra +1
Computer Science · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #I.2.8 #J.4 #Multiagent Systems (cs.MA) #cs.DS #cs.MA

paper · pdf · doi:10.48550/arxiv.cs/0509061

arxiv created 2007/06/23 · arxiv updated 2009/12/01

Abstract

In the year 1876 the mathematician Charles Dodgson, who wrote fiction under the now more famous name of Lewis Carroll, devised a beautiful voting system that has long fascinated political scientists. However, determining the winner of a Dodgson election is known to be complete for the Θ₂^p level of the polynomial hierarchy. This implies that unless P=NP no polynomial-time solution to this problem exists, and unless the polynomial hierarchy collapses to NP the problem is not even in NP. Nonetheless, we prove that when the number of voters is much greater than the number of candidates--although the number of voters may still be polynomial in the number of candidates--a simple greedy algorithm very frequently finds the Dodgson winners in such a way that it ``knows'' that it has found them, and furthermore the algorithm never incorrectly declares a nonwinner to be a winner.

Related

• Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP
• Dodgson's Rule Approximations and Absurdity
• Exact Complexity of the Winner Problem for Young Elections
• On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time
• A O(log m), deterministic, polynomial-time computable approximation of Lewis Carroll's scoring rule