Improving Dodgson scoring techniques

Show full item record

Title: Improving Dodgson scoring techniques
Author: Covey, Jason A.
Abstract: The Dodgson score problem is part of the Dodgson election scheme invented by Charles Dodgson and presented in his manuscript. One of the system's strengths (and motivations for its study) is that it satisfies the Condorcet criterion (which states that any candidate who defeats all other candidates in pairwise elections will be declared the winner). It is unfortunate, though, that in a given election no Condorcet winner may exist. Dodgson's election system chooses the winner "closest" to being the Condorcet winner in the sense that it requires the shortest sequence of edits (swapping of adjacent candidates in the voters' preference rankings) to the votes in order to make it one. The length of this sequence is known as the Dodgson score. The problem of finding the Dodgson score of a candidate is computationally intractable. Thus an approximation is necessary. This paper puts forth MCDodgsonScore, a polynomialtime computable (ln(m) + 1)-approximation of that problem. This approximation is optimal, meaning that an approximation with an asymptotically tighter error bound does not exist. MCDodgsonScore builds on a technique introduced by Homan and Hemaspaandra in 2006. A nice feature of MCDodgsonScore is that, when treated as its own voting rule, it will also satisfy the Condorcet criterion.
Record URI: http://hdl.handle.net/1850/10820
Date: 2009

Files in this item

Files Size Format View
22999_pdf_20080 ... 11DE-9B42-E16EF0E6BF1D.pdf 244.8Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse