Approximability and Computational Feasibility of Dodgson's Rule

by McCabe-Dansted, John C.

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


Date of Publication:01/01/2006

© 2009 All Rights Reserved.