Aigaion: RACTI / RU1 Technical Report Series (Web Based)

[RACTI-RU1-2009-3] Caragiannis, Ioannis, Covey, J.A., Feldman, M., Homan, C.M., Kaklamanis, Christos, Karanikolas, A.D., Procaccia, A.D. and Rosenschein, J.S., On the Approximability of Dodgson and Young Elections, in: 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), 2009.
Abstract: The voting rules proposed by Dodgson and Young are both designed to nd the alternative closest to being a Condorcet winner, according to two dierent 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.
[RACTI-RU1-2010-20] Caragiannis, Ioannis, Kaklamanis, Christos, Karanikolas, Nikos and Procaccia, A.D., Socially desirable approximations for Dodgson's voting rule, in: 11th ACM Conference on Electronic Commerce, EC 2010, pages 253-262, 2010.
Abstract: In 1876 Charles Lutwidge Dodgson suggested the intriguing voting rule that today bears his name. Although Dodgson's rule is one of the most well-studied voting rules, it suffers from serious deciencies, both from the computational point of view\|it is NP-hard even to approximate the Dodgson 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 denitive answers to these questions. We design 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 several additional social choice properties; for these properties, we prove that algorithms with an approximation ratio that depends only on m do not exist.
[RACTI-RU1-2011-45] Caragiannis, Ioannis, Kaklamanis, Christos, Karanikolas, Nikos and Procaccia, A.D., Socially desirable approximations for Dodgson┬ voting rule, in: ACM Transactions on Algorithms, 2011.
Abstract: 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 deciencies, 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 denitive 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.