research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleOn the Approximability of Dodgson and Young Elections
Bibtex cite IDRACTI-RU1-2009-3
Booktitle 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)
Year published 2009
Address New York, New York
Note to appear
The voting rules proposed by Dodgson and Young are both designed to nd the alternative closest to being a Condorcet winner, according to two di erent notions of proximity; the score of a given alternative is known to be hard to compute under either rule. In this paper, we put forward two algorithms for ap- proximating the Dodgson score: an LP-based randomized rounding algorithm and a deterministic greedy algorithm, both of which yield an O(logm) approximation ratio, where m is the number of alternatives; we observe that this result is asymptotically optimal, and further prove that our greedy algorithm is optimal up to a factor of 2, unless problems in NP have quasi-polynomial time algorithms. Although the greedy algorithm is computationally superior, we argue that the randomized rounding algorithm has an advantage from a social choice point of view. Further, we demonstrate that computing any reasonable approximation of the ranking produced by Dodgson's rule is NP-hard. This result provides a complexity-theoretic explanation of sharp discrepancies that have been observed in the Social Choice Theory literature when comparing Dodgson elections with simpler voting rules. Finally, we show that the problem of calculating the Young score is NP-hard to approximate by any factor. This leads to an inapproximability result for the Young ranking.
Caragiannis, Ioannis
Covey, J.A.
Feldman, M.
Homan, C.M.
Kaklamanis, Christos
Karanikolas, A.D.
Procaccia, A.D.
Rosenschein, J.S.
soda09a.pdf (main file)
Publication ID519