Abstract
It is known that Dodgson’s rule is computationally very demanding. Tideman (Soc Choice Welf 4:185–206, 1987) suggested an approximation to it but did not investigate how often his approximation selects the Dodgson winner. We show that under the Impartial Culture assumption the probability that the Tideman winner is the Dodgson winner converges to 1 as the number of voters increase. However we show that this convergence is not exponentially fast. We suggest another approximation—we call it Dodgson Quick—for which this convergence is exponentially fast. Also we show that the Simpson and Dodgson rules are asymptotically different.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anderson, TW: An introduction to multivariate statistical analysis, 2nd edn. Wiley, Brisbane (1984)
Bartholdi, III, Tovey, CA, Trick, MA: Voting schemes for which it can be difficult to tell who won the election. Soc Choice Welf 6, 157– (1989)
Berg, S: Paradox of voting under an urn model: the effect of homogeneity. Public Choice 47, 377–387 (1985)
Black, D: Theory of committees and elections. Cambridge University Press, Cambridge (1958)
Debord, B: Caractérisation des matrices des préférences nettes et méthodes d’agrégation associées. (Characterization of net preference matrices and related aggregation methods). Math Sci Hum 97, 5–17 (1987)
Dembo A, Zeitouni O (1993) Large deviations techniques. Johns and Barlett
Dodgson CL (1876) A method for taking votes on more than two issues. Clarendon Press, Oxford. Reprinted in Black (1958) with discussion
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– (1997)
Homan CM, Hemaspaandra LA (2005) Guarantees for the success frequency of an algorithm for finding dodgson-election winners. Technical Report Technical Report TR-881, Department of Computer Science, University of Rochester, Rochester, NY. http://urresearch.rochester.edu/retrieve/4794/tr881.pdf
Klamler C (2004) The Dodgson ranking and the Borda count: a binary comparison. Math Soc Sci 48(1):103–108. http://ideas.repec.org/a/eee/matsoc/v48y2004i1p103-108.html
Laslier, J-F: Tournament solutions and majority voting. Springer, Berlin (1997)
McCabe-Dansted JC (2006) Feasibility and approximability of Dodgson’s rule. Master’s thesis, Auckland University. http://dansted.org/thesis06
McCabe-Dansted JC, Slinko A (2006) Exploratory analysis of similarities between social choice rules. Group Decis Negot 15:1–31. http://dx.doi.org/10.1007/s00355-005-0052-4
Ratliff TC (2001) A comparison of Dodgson’s method and Kemeny’s rule. Soc Choice Welf 18(1):79–89. ISSN 0176-1714 (Print) 1432-217X (Online). http://dx.doi.org/10.1007/s003550000060
Ratliff TC (2002) A comparison of Dodgson’s method and the Borda count. Econ Theory 20(2):357–372. ISSN 0938-2259 (Print) 1432-0479 (Online). http://dx.doi.org/10.1007/s001990100218
Shah R (2003) Statistical mappings of social choice rules. Master’s thesis, Stanford University
Simpson, PB: On defining areas of voter choice: Professor tullock on stable voting. Q J Econ 83(3), 478–490 (1969)
Tideman, TN: Independence of clones as a criterion for voting rules. Soc Choice Welf 4, 185– (1987)
Walpole, RE, Myers, RH: Probability and statistics for engineers and scientists. Maxwell Macmillian International, Sydney (1993)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
McCabe-Dansted, J.C., Pritchard, G. & Slinko, A. Approximability of Dodgson’s rule. Soc Choice Welfare 31, 311–330 (2008). https://doi.org/10.1007/s00355-007-0282-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00355-007-0282-8