Abstract:
Condorcet 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 Dodgson (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 complete for parallel access to NP, and hence is not in NP unless the polynomial heirachy collapses. 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 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.