Determining the Winner of a Dodgson Election is Hard
Frances A. Rosamond
Charles Darwin University, Australia
Charles Darwin University, Australia
2014/03/25 Tuesday 4PM -5PM
Room 1409
Room 1409
Computational social choice is a growing discipline at the interface of social choice theory and computer science. It is concerned with the application of computational techniques to the study of social choice mechanisms, and with the integration of social choice paradigms into computing. Several problems have been investigated in the framework of parameterized complexity. This talk will describe the election scheme of Charles Dodgson. In 1876 the mathematician Charles Dodgson (better known as Lewis Carroll) formulated a rule that defines the winner of an election even if there is no Condorcet winner. A candidate who beats every other candidate in pairwise comparison is said to be a Condorcet winner. Unfortunately, an election may have a cyclic structure (candidate a beats b, candidate b beats c and c beats a), and therefore no candidate who beats all others in pairwise comparison. The Dodgson Score measures how close a candidate is to being a Condorcet winner. Candidates with a minimum Dodgson Score are the election winners. As are many election methods, Dodgson Score is NP-hard. This talk discusses the complexity of Dodgson Score in the parameterized framework. We give a reduction from Multi-Colored Clique to show that Dodgson Score, parameterized by the number of votes, is W[1]-hard. When parameterized by the number of swaps, Dodgson Score is FPT, but we show by polynomial parameter transformation that it has no polynomial kernel.