Citation:
Ariel D. Procaccia, Michal Feldmany, and Jeffrey S. Rosenschein. “Approximability And Inapproximability Of Dodgson And Young Elections”. Discussion Papers 2007. Web.
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.