Approximability of Dodgson's rule

John C. McCabe-Dansted, Geoffrey Pritchard, Arkadii Slinko


It is known that Dodgson's rule is computationally very demanding.
Tideman (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 tend to 1. However we show
that the convergence of this probability to 1 is slow. We suggest
another approximation - we call it Dodgson Quick - for which this
convergence is exponentially fast. Also we show that Simpson and
Dodgson rules are asymptotically different. We formulate, and heavily
use in construction of examples, the generalization of McGarvey's
theorem (1953) for weighted majority relations.

Dodgson's rule, McGarvey theorem

Math Review Classification
Primary 91B12

Last Updated
17 June, 2006


This article is available in: