# Approximability and Computational Feasibility of Dodgson's Rule

Abstract (Summary)

Condorcet1 proposed that a winner of an election is not legitimate unless a majority of the
population prefer that alternative to all other alternatives. However such a winner does
not always exist. A number of voting rules have been proposed which select the Condorcet
winner if it exists, and otherwise selects an alternative that is in some sense closest
to being a Condorcet Winner; a prime example is the rule proposed by Dodgson2(1876).
Unfortunately, Bartholdi et al. (1989) proved that finding the Dodgson winner is an
NP-hard problem. Hemaspaandra et al. (1997) refined this result by proving that it is ?p
2-
complete and hence is not NP-complete unless ?p
2=NP. For this reason, we investigate
the asymptotic behaviour of approximations to the Dodgson rule as the number of agents
gets large.
Under the assumption that all votes are independent and equiprobable, the probability
that the Tideman (1987) approximation picks the Dodgson winner does asymptotically
converge to 1, but not exponentially fast. We propose a new approximation that does exhibit
exponential convergence, and we can quickly verify that it has chosen the Dodgson
winner; this allows us to choose the true Dodgson winner with O(ln n) expected running
time for a fixed number of alternatives m and n agents.
McGarvey (1953) proved that all tournaments are the majority relations for some society.
We have proved a generalisation of this theorem for weighted tournaments. We
find that this generalisation is useful for simplifying proofs relating to rules which use
the weighted majority relation.
Bartholdi et al. (1989) found that we can calculate the Dodgson Score using an ILP
that requires no more than m!m variables, we present an improved ILP that requires less
than (m ? 1)!e variables (e ? 2.71). We discover that we can solve this ILP in O(ln n)
arithmetic operations of O(ln n) bits in size. Relaxing the integer constraints results in
a new polynomial time rule. In 43 million simulations this new rule failed to pick the
1
Marie-Jean-Antoine-Nicolas de Caritat, Marquis de Condorcet. (1743–1794)
2
Charles Lutwidge Dodgson (1832–1898), better known as Lewis Carroll.
i
Dodgson winner only once, and only given many (25) alternatives. Unlike the Dodgson
rule, this rule can break ties in favor of alternatives that are in some sense fractionally
better.
We show that Dodgson Score admits no constant error approximation unless P=NP,
and admits no Polynomial Time Approximation Scheme (PTAS) for Dodgson Score unless
W[2]=FPT.
ii
Bibliographical Information:

Advisor:Dr A. Slinko; Dr G. Pritchard

School:The University of Auckland / Te Whare Wananga o Tamaki Makaurau

School Location:New Zealand

Source Type:Master's Thesis

Keywords:dodgson tideman approximability feasibility voting dq quick relaxed fields of research 230000 mathematical sciences 230100 mathematics 230200 statistics 340000 economics 349900 other 360000 policy and political science 369900

ISBN:

Date of Publication:01/01/2006