Lecture Notes in Computer Science, 2006, Volume 4162/2006, 528-539, DOI: 10.1007/11821069_46

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

Christopher M. Homan and Lane A. Hemaspaandra

View Related Documents

Abstract

Dodgson’s election system elegantly satisfies the Condorcet criterion. However, determining the winner of a Dodgson election is known to be Qp2{\mathrm{\Theta}^{\mathit{p}}_2}-complete ([1], see also [2]), which 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.

Fulltext Preview

Image of the first page of the fulltext document