Approximability and Inapproximability of Dodgson and Young Elections

Authors: 
Ariel D. Procaccia, Michal Feldmany and Jeffrey S. Rosenschein
Abstract: 

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.

Date: 
October, 2007
Published in: 
Number: 
466