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:Article
Entered by:chita
TitleSocially desirable approximations for Dodgson¢s voting rule
Bibtex cite IDRACTI-RU1-2011-45
Journal ACM Transactions on Algorithms
Year published 2011
Note to appear
Keywords Social choice,Dodgson's voting rule,Approximation algorithms
In 1876 Charles Lutwidge Dodgson suggested the intriguing voting rule that today bears his name. Although Dodg- son's rule is one of the most well-studied voting rules, it suf- fers from serious de ciencies, both from the computational point of view|it is NP-hard even to approximate the Dodg- son score within sublogarithmic factors|and from the social choice point of view|it fails basic social choice desiderata such as monotonicity and homogeneity. In a previous paper [Caragiannis et al., SODA 2009] we have asked whether there are approximation algorithms for Dodgson's rule that are monotonic or homogeneous. In this paper we give de nitive answers to these questions. We de- sign a monotonic exponential-time algorithm that yields a 2-approximation to the Dodgson score, while matching this result with a tight lower bound. We also present a monotonic polynomial-time O(logm)-approximation algorithm (where m is the number of alternatives); this result is tight as well due to a complexity-theoretic lower bound. Furthermore, we show that a slight variation of a known voting rule yields a monotonic, homogeneous, polynomial-time O(mlogm)- approximation algorithm, and establish that it is impossible to achieve a better approximation ratio even if one just asks for homogeneity. We complete the picture by studying sev- eral additional social choice properties; for these properties, we prove that algorithms with an approximation ratio that depends only on m do not exist.
Caragiannis, Ioannis
Kaklamanis, Christos
Karanikolas, Nikos
Procaccia, A.D.
Caragiannis10b.pdf (main file)
Publication ID897