Dodgson's method

Voting systems
Part of the Politics series
Plurality/Majoritarian Simple majoritarianism Limited voting Single non-transferable vote Plurality First-past-the-post Two-round Exhaustive ballot Preferential/ranked/ordinal systems Borda count Bucklin voting Condorcet methods (Copeland's, Dodgson's, Kemeny-Young, Minimax, Nanson's, Ranked pairs, Schulze) Coombs' method Instant-runoff (alternative vote) Contingent vote Oklahoma primary electoral system Cardinal/graded/rated systems Approval voting Proportional approval voting Sequential proportional approval voting Satisfaction approval voting Majority judgment Range voting
Proportional Representation Party-list (Open lists, Closed lists, Local lists) Highest averages (D'Hondt, Sainte-Laguë) Largest remainder (Hare, Droop, Imperiali, Hagenbach-Bischoff) Single transferable vote (CPO-STV, Gregory, Schulze STV, Wright)
Mixed-Member Mixed-member proportional Majority bonus system Additional member system Scorporo, Av+ Parallel voting Majoritarian representation Plurality-at-large Preferential block voting General ticket
Other Proxy voting Delegable voting Delegated voting Random selection Sortition Random ballot Social choice theory Arrow's theorem Gibbard–Satterthwaite theorem Voting system criteria Public choice theory (separate but related) Multiple Ballot Voting Cumulative voting
Politics portal

Dodgson's method is a voting system proposed by the author, mathematician and logician Charles Dodgson, better known as Lewis Carroll. The method is to extend the Condorcet method by swapping candidates until a Condorcet winner is found. The winner is the candidate which requires the minimum number of swaps. Dodgson proposed this voting scheme in his 1876 work "A method of taking votes on more than two issues". Given an integer k and an election, it is NP-complete to determine whether a candidate can become a Condorcet winner with fewer than k swaps.

Description

In Dodgson's method, each voter submits an ordered list of all candidates according to their own preference (from best to worst). The winner is defined to be the candidate for whom we need to perform the minimum number of pairwise swaps (added over all candidates) before they become a Condorcet winner. In particular, if there is already a Condorcet winner, they win the election.

In short, we must find the voting profile with minimum Kendall tau distance from the input, such that it has a Condorcet winner; they are declared the victor. Computing the winner or even the Dodgson score of a candidate (the number of swaps needed to make him a winner) is a P^NP_||-complete problem.^[1]

References

↑ J. Bartholdi III, C. A. Tovey, and M. A. Trick, "Voting schemes for which it can be difficult to tell who won the election", Social Choice and Welfare, Vol. 6, No. 2 (1989), pp. 157–165.

This article is issued from Wikipedia - version of the Monday, November 16, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.