Dodgson's method

Dodgson's method is an electoral 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.

Electoral systems
Part of the Politics series
Plurality/majoritarian Plurality First-past-the-post Single non-transferable vote Limited voting Plurality-at-large (block voting) General ticket Multi-round voting Two-round Exhaustive ballot Ranked / preferential systems Instant-runoff (alternative vote) Contingent vote Coombs' method Condorcet methods (Copeland's, Dodgson's, Kemeny–Young, Minimax, Nanson's, ranked pairs, Schulze, Alternative Smith) Positional voting (Borda count, Nauru/Dowdall method, Eurovision Song Contest) Bucklin voting Oklahoma primary electoral system Preferential block voting Cardinal / graded systems Score voting Approval voting (unified primary) Satisfaction approval voting Majority judgment STAR voting
Proportional representation Party-list (open lists, closed lists, local lists) Highest averages (D'Hondt, Sainte-Laguë, Huntington–Hill) Largest remainder (Hare, Droop, Imperiali, Hagenbach-Bischoff) Proportional forms of instant runoff voting Single transferable vote (Gregory, Wright) Proportional forms of Condorcet methods CPO-STV Schulze STV Proportional forms of approval voting Proportional approval voting Sequential proportional approval voting Biproportional apportionment Fair majority voting
Mixed systems Mixed-member proportional Additional member system Parallel voting (mixed-member majoritarian) Scorporo Majority bonus Alternative Vote Plus Dual-member proportional Rural–urban proportional
Other systems and related theory Cumulative voting Binomial voting Proxy voting Delegated voting Random selection (sortition, random ballot) Comparison of electoral systems Social choice theory Arrow's theorem Gibbard–Satterthwaite theorem Public choice theory
Politics portal

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 in each ballot (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; then, the Condorcet winner is declared the victor. Computing the winner or even the Dodgson score of a candidate (the number of swaps needed to make that candidate a winner) is an NP-hard problem [1] by reduction from Exact Cover by 3-Sets (X3C).[2]

gollark: Suuuuuure.

gollark: Well, ALL is gollark.

gollark: Well, obviously my submission is.

gollark: Helloboious ones.

gollark: Yes, that's right, VERY INCONSISTENT NATURAL LANGUAGE SUPPORT.

References

Bartholdi, J.; Tovey, C. A.; Trick, M. A. (April 1989). "Voting schemes for which it can be difficult to tell who won the election". Social Choice and Welfare. 6 (2): 157–165. doi:10.1007/BF00303169. The article only directly proves NP-hardness, but it is clear that the decision problem is in NP since given a candidate and a list of k swaps, you can tell whether that candidate is a Condorcet winner in polynomial time.
Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability. W.H. Freeman Co., San Francisco.

Electoral systems
Part of the politics and election series
Single-winner voting system	Approval voting Unified Primary Borda count Bucklin voting Contingent vote Supplementary vote Condorcet methods Coombs' method Copeland's method Dodgson's method Kemeny–Young method Minimax Condorcet Nanson's method Ranked pairs Schulze method Exhaustive ballot First-past-the-post voting Instant-runoff (ranked choice) voting Majority judgment Simple majoritarianism Plurality Positional voting system Score voting STAR voting Two-round system
Proportional representation	CPO-STV Dual member Hare-Clark Highest averages method Webster/Sainte-Laguë D'Hondt Largest remainder method Mixed-member Party-list Schulze STV Single transferable vote
Semi-proportional representation	Parallel voting Single non-transferable vote Cumulative voting Limited voting Proportional approval voting Sequential proportional approval voting Satisfaction approval voting Alternative vote plus
Usage	Table of voting systems by country
Voting system criteria	Comparison Condorcet criterion Condorcet loser criterion Consistency criterion Independence of clones Independence of irrelevant alternatives Independence of Smith-dominated alternatives Later-no-harm criterion Majority criterion Majority loser criterion Monotonicity criterion Mutual majority criterion Pareto efficiency Participation criterion Plurality criterion Resolvability criterion Reversal symmetry Smith criterion
Voting system quotas	Droop quota Hagenbach-Bischoff quota Hare quota Imperiali quota
Other	Ballot Election threshold First-preference votes Spoilt vote Sortition
Portal — Project

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.