Approximability and Inapproximability of Dodgson and Young Elections

Ariel D. Procaccia, Michal Feldmany and Jeffrey S. Rosenschein

The voting rules proposed by Dodgson and Young are both designed to find the candidate closest to being a Condorcet winner, according to two different notions of proximity; the score of a given candidate is known to be hard to compute under both rules. In this paper, we put forward an LP-based randomized rounding algorithm which yields an O(log m) approximation ratio for the Dodgson score, where m is the number of candidates. Surprisingly, we show that the seemingly simpler Young score is NP-hard to approximate by any factor.

October, 2007
Published in: