Skip to main content
SpringerLink
Log in

Guarantees for the success frequency of an algorithm for finding Dodgson-election winners

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

In the year 1876 the mathematician Charles Dodgson, who wrote fiction under the now more famous name of Lewis Carroll, devised a beautiful voting system that has long fascinated political scientists. However, determining the winner of a Dodgson election is known to be complete for the Θ p2 level of the polynomial hierarchy. This implies that unless P=NP no polynomial-time solution to this problem exists, and unless the polynomial hierarchy collapses to NP the problem is not even in NP. Nonetheless, we prove that when the number of voters is much greater than the number of candidates—although the number of voters may still be polynomial in the number of candidates—a simple greedy algorithm very frequently finds the Dodgson winners in such a way that it “knows” that it has found them, and furthermore the algorithm never incorrectly declares a nonwinner to be a winner.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Ausiello, G., Crescenzi, P., Protasi, M.: Approximate solution of NP optimization problems. Theor. Comput. Sci. 150(1), 1–55 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  • Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley–Interscience, New York (2000)

    MATH  Google Scholar 

  • Black, D.: The Theory of Committees and Elections. Cambridge University Press, Cambridge (1958)

    MATH  Google Scholar 

  • Brown, D.: A probabilistic analysis of a greedy algorithm arising from computational biology. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 206–207. ACM, New York (2001)

    Google Scholar 

  • Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. SIAM J. Comput. 36(4), 1119–1159 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  • Bartholdi III, J., Tovey, C., Trick, M.: Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welf. 6(2), 157–165 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  • Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The boolean hierarchy I: structural properties. SIAM J. Comput. 17(6), 1232–1252 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  • Chernoff, H.: A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23(4), 493–509 (1952)

    Article  MATH  MathSciNet  Google Scholar 

  • Chang, L., Korsh, J.: Canonical coin changing and greedy solutions. J. ACM 23(3), 418–422 (1976)

    MATH  MathSciNet  Google Scholar 

  • Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press/McGraw–Hill, Cambridge/New York (2001)

    MATH  Google Scholar 

  • Conitzer, V., Sandholm, T.: Nonexistence of voting rules that are usually hard to manipulate. In: Proceedings of the 21st National Conference on Artificial Intelligence, pp. 627–634. AAAI Press, Menlo Park (2006)

    Google Scholar 

  • de Borda, J.: Mémoire sur les élections au scrutin. Hist. Acad. Roy. Sci. Ann. 1781 (1784)

  • de Caritat, M.J.A.N.: Marquis de Condorcet. Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix (1785). Facsimile reprint of original published in Paris, 1972, by the Imprimerie Royale

  • Dodgson, C.: A method of taking votes on more than two issues. Pamphlet printed by the Clarendon Press, Oxford, and headed “not yet published” (see the discussions in McLean and Urken (1995) and Black (1958), both of which reprint this paper) (1876)

  • Downey, R.: Parameterized complexity for the skeptic. In: Proceedings of the 18th Annual IEEE Conference on Computational Complexity, pp. 147–168. IEEE Computer Society, Los Alamitos (2003)

    Chapter  Google Scholar 

  • Downey, R., Fellows, M.: Parameterized Complexity. Springer, Berlin (1999)

    Google Scholar 

  • Erdélyi, G., Hemaspaandra, L., Rothe, J., Spakowski, H.: On approximating optimal weighted lobbying, and frequency of correctness versus average-case polynomial time. Technical Report TR-914, Department of Computer Science, University of Rochester, Rochester, NY (March 2007)

  • Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: The complexity of bribery in elections. In: Proceedings of the 21st National Conference on Artificial Intelligence, pp. 641–646. AAAI Press, Menlo Park (2006a)

    Google Scholar 

  • Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: How hard is bribery in elections? Technical Report TR-895, Department of Computer Science, University of Rochester, Rochester, NY, April 2006. Revised (September 2006b)

  • Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Llull and Copeland voting broadly resist bribery and control. In: Proceedings of the 22nd National Conference on Artificial Intelligence, pp. 724–730. AAAI Press, Menlo Park (2007)

  • Goldberg, A., Marchetti-Spaccamela, A.: On finding the exact solution of a zero-one knapsack problem. In: Proceedings of the 16th ACM Symposium on Theory of Computing, pp. 359–368. ACM, New York (1984)

    Google Scholar 

  • Hägele, G., Pukelsheim, F.: The electoral writings of Ramon Llull. Stud. Lulliana 41(97), 3–38 (2001)

    Google Scholar 

  • Hemachandra, L.: The strong exponential hierarchy collapses. J. Comput. Syst. Sci. 39(3), 299–322 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  • Hemaspaandra, E., Hemaspaandra, L.: Computational politics: electoral systems. In: Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 1893, pp. 64–83. Springer, Berlin (2000)

    Google Scholar 

  • Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. J. ACM 44(6), 806–825 (1997)

    MATH  MathSciNet  Google Scholar 

  • Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of Kemeny elections. Theor. Comput. Sci. 349(3), 382–391 (2005)

    MATH  MathSciNet  Google Scholar 

  • Homan, C., Hemaspaandra, L.: Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. In: Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 4162, pp. 528–539. Springer, Berlin (2006)

    Google Scholar 

  • Impagliazzo, R.: A personal view of average-case complexity. In: Proceedings of the 10th Structure in Complexity Theory Conference, pp. 134–147. IEEE Computer Society, Los Alamitos (1995)

    Google Scholar 

  • Kadin, J.: The polynomial time hierarchy collapses if the boolean hierarchy collapses. SIAM J. Comput. 17(6), 1263–1282 (1988). Erratum appears in the same journal 20(2), 404

    Article  MATH  MathSciNet  Google Scholar 

  • Kaporis, A., Kirousis, L., Lalas, E.: The probabilistic analysis of a greedy satisfiability algorithm. In: Proceedings of the 10th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 2461, pp. 574–585. Springer, Berlin (2002)

    Google Scholar 

  • Lenstra, H. Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  • Levin, L.: Average case complete problems. SIAM J. Comput. 15(1), 285–286 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  • McCabe-Dansted, J., Pritchard, G., Slinko, A.: Approximability of Dodgson’s rule. In: Endriss, U., Lang, J. (eds.) Proceedings of the 1st International Workshop on Computational Social Choice, pp. 331–344. Universiteit van Amsterdam (2006). Available online at staff.science.uva.nl/~ulle/COMSOC-2006/proceedings.html

  • McLean, I., Urken, A.: Classics of Social Choice. University of Michigan Press, Ann Arbor (1995)

    Google Scholar 

  • Nanson, E.: Methods of election. Trans. Proc. Roy. Soc. Vic. 19, 197–240 (1882)

    Google Scholar 

  • Niedermeier, R.: Invitation to fixed-parameter algorithms. Habilitation thesis, University of Tübingen (2002)

  • Procaccia, A., Rosenschein, J.: Junta distributions and the average-case complexity of manipulating elections. J. Artif. Intell. Res. 28, 157–181 (2007)

    MATH  MathSciNet  Google Scholar 

  • Protasi, M., Talamo, M.: A new probabilistic model for the study of algorithmic properties of random graph problems. In: Proceedings of the 4th Conference on Fundamentals of Computation Theory. Lecture Notes in Computer Science, vol. 158, pp. 360–367. Springer, Berlin (1983)

    Google Scholar 

  • Papadimitriou, C., Zachos, S.: Two remarks on the power of counting. In: Proceedings of the 6th GI Conference on Theoretical Computer Science. Lecture Notes in Computer Science, vol. 145, pp. 269–276. Springer, Berlin (1983)

    Google Scholar 

  • Raffaelli, G., Marsili, M.: Statistical mechanics model for the emergence of consensus. Phys. Rev. E 72(1), 016114 (2005)

    Article  Google Scholar 

  • Rothe, J., Spakowski, H., Vogel, J.: Exact complexity of the winner problem for Young elections. Theory Comput. Syst. 36(4), 375–386 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  • Sankoff, D., Kruskal, J. (eds.): Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Computation. Addison–Wesley, Reading (1983)

    Google Scholar 

  • Slavik, P.: A tight analysis of the greedy algorithm for set cover. J. Algorithms 25(2), 237–254 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  • Spielman, D., Teng, S.: Smoothed analysis: Why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385–463 (2004)

    MathSciNet  Google Scholar 

  • Spakowski, H., Vogel, J.: Θ p2 -completeness: A classical approach for new results. In: Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 1974, pp. 348–360. Springer, Berlin (2000)

    Google Scholar 

  • Spakowski, H., Vogel, J.: The complexity of Kemeny’s voting system. In: Proceedings of the Workshop Argentino de Informática Teórica. Anales Jornadas Argentinas de Informática e Investigación Operativa, vol. 30, pp. 157–168. SADIO (2001)

  • Tideman, T.: Independence of clones as a criterion for voting rules. Soc. Choice Welf. 4(3), 185–206 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  • Trevisan, L.: Lecture notes on computational complexity. www.cs.berkeley.edu/~luca/notes/complexitynotes02.pdf (Lecture 12) (2002)

  • Wagner, K.: More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci. 51(1–2), 53–80 (1987)

    Article  MATH  Google Scholar 

  • Wagner, K.: Bounded query classes. SIAM J. Comput. 19(5), 833–846 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  • Wang, J.: Average-case computational complexity theory. In: Hemaspaandra, L., Selman, A. (eds.) Complexity Theory Retrospective II, pp. 295–328. Springer, Berlin (1997a)

    Google Scholar 

  • Wang, J.: Average-case intractable NP problems. In: Du, D., Ko, K. (eds.) Advances in Languages, Algorithms, and Complexity, pp. 313–378. Kluwer Academic, Dordrecht (1997b)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Rochester Institute of Technology, Rochester, NY, 14623, USA

    Christopher M. Homan

  2. Department of Computer Science, University of Rochester, Rochester, NY, 14627, USA

    Lane A. Hemaspaandra

Authors
  1. Christopher M. Homan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lane A. Hemaspaandra
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christopher M. Homan.

Additional information

A preliminary version of this paper was presented at the 2006 MFCS conference (Homan and Hemaspaandra in Lecture Notes in Computer Science, vol. 4162, 2006) and the 2006 COMSOC workshop.

L.A. Hemaspaandra’s research was supported in part by grant NSF-CCF-0426761, the Alexander von Humboldt Foundation’s TransCoop program, and a Friedrich Wilhelm Bessel Research Award. Work done in part while visiting Heinrich-Heine-Universität Düsseldorf.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Homan, C.M., Hemaspaandra, L.A. Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. J Heuristics 15, 403–423 (2009). https://doi.org/10.1007/s10732-007-9068-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-007-9068-5

Keywords

Search

Navigation