On the approximability of Dodgson and Young elections

ABSTRACT

The voting rules proposed by Dodgson and Young are both designed to find the alternative closest to being a Condorcet winner, according to two different 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 approximating the Dodgson score: an LP-based randomized rounding algorithm and a deterministic greedy algorithm, both of which yield an O(log m) 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.

REFERENCES

• 1: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 2: J. Bartholdi, C. A. Tovey, and M. A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6:157--165, 1989.
• 3: Piotr Berman , Marek Karpinski, On Some Tighter Inapproximability Results (Extended Abstract), Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.200-209, July 11-15, 1999
• 4: Nadja Betzler , Jiong Guo , Rolf Niedermeier, Parameterized Computational Complexity of Dodgson and Young Elections, Proceedings of the 11th Scandinavian workshop on Algorithm Theory, July 02-04, 2008, Gothenburg, Sweden [doi>10.1007/978-3-540-69903-3_36]
• 5: D. Black. Theory of Committees and Elections. Cambridge University Press, 1958.
• 6: I. Caragiannis, J. A. Covey, M. Feldman, C. M. Homan, C. Kaklamanis, N. Karanikolas, A. D. Procaccia, and J. S. Rosenschein. On the approximability of Dodgson and Young elections. Technical report 2008--80, Leibniz Center for Research in Computer Science, 2008. Available from: http://leibniz.cs.huji.ac.il/tr/1137.full.pdf.
• 7: V. Conitzer. Computing Slater rankings using similarities among candidates. In AAAI, pages 613--619, 2006.
• 8: V. Conitzer, A. Davenport, and J. Kalagnanam. Improved bounds for computing Kemeny rankings. In AAAI, pages 620--626, 2006.
• 9: Don Coppersmith , Lisa Fleischer , Atri Rudra, Ordering by weighted number of wins gives a good ranking for weighted tournaments, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.776-782, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109642]
• 10: C. d'Aspremont and B. Peleg. Ordinal Bayesian incentive compatible representations of committees. Social Choice and Welfare, 5:261--279, 1988.
• 11: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 12: A. Gibbard. Manipulation of voting schemes. Econometrica, 41:587--602, 1973.
• 13: A. Gibbard. Manipulation of schemes that mix voting with chance. Econometrica, 45:665--681, 1977.
• 14: Edith Hemaspaandra , Lane A. Hemaspaandra , Jörg Rothe, Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP, Journal of the ACM (JACM), v.44 n.6, p.806-825, Nov. 1997 [doi>10.1145/268999.269002]
• 15: C. Homan and L. A. Hemaspaandra. Guarantees for the success frequency of an algorithm for finding Dodgson election winners. In MFCS, pages 528--539, 2006.
• 16: K. Jogdeo and S. Samuels. Monotone convergence of binomial probabilities and a generalization of Ramanujan's equation. Annals of Mathematical Statistics, 39:1191--1195, 1968.
• 17: Claire Kenyon-Mathieu , Warren Schudy, How to rank with few errors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250806]
• 18: C. Klamler. A comparison of the Dodgson method and the Copeland rule. Economics Bulletin, 4(8):1--7, 2003.
• 19: C. Klamler. The Dodgson ranking and its relation to Kemeny's method and Slater's rule. Social Choice and Welfare, 23(1):91--102, 2004.
• 20: C. Klamler. The Dodgson ranking and the Borda count: a binary comparison. Mathematical Social Sciences, 48(1):103--108, 2004.
• 21: H. W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8:538--548, 1983.
• 22: J. C. McCabe-Dansted. Approximability and computational feasibility of Dodgson's rule. Master's thesis, University of Auckland, 2006.
• 23: J. C. McCabe-Dansted, G. Pritchard, and A. M. Slinko. Approximability of Dodgson's rule. In COMSOC, pages 331--344, 2006.
• 24: N. Nisan. Introduction to mechanism design (for computer scientists). In N. Nisan, T. Roughgarden, É. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, chapter 9. Cambridge University Press, 2007.
• 25: A. D. Procaccia, A. Zohar, Y. Peleg, and J. S. Rosenschein. Learning voting trees. In AAAI, pages 110--115, 2007.
• 26: Ariel D. Procaccia , Aviv Zohar , Jeffrey S. Rosenschein, Automated design of scoring rules by learning from examples, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 27: Sridhar Rajagopalan , Vijay V. Vazirani, Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs, SIAM Journal on Computing, v.28 n.2, p.525-540, April 1999 [doi>10.1137/S0097539793260763]
• 28: T. C. Ratliff. A comparison of Dodgson's method and Kemeny's rule. Social Choice and Welfare, 18(1):79--89, 2001.
• 29: T. C. Ratliff. A comparison of Dodgson's method and the Borda count. Economic Theory, 20(2):357--372, 2002.
• 30: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 31: J. Rothe, H. Spakowski, and J. Vogel. Exact complexity of the winner problem for young elections. Theory of Computing Systems, 36(4):375--386, 2003.
• 32: M. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10:187--217, 1975.
• 33: N. Tideman. Collective Decisions and Voting: The Potential for Public Choice. Ashgate, 2006.
• 34: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 35: H. P. Young. Extending Condorcet's rule. Journal of Economic Theory, 16:335--353, 1977.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms