Dodgson's method is an

electoral system An electoral or voting system is a set of rules used to determine the results of an election. Electoral systems are used in politics to elect governments, while non-political elections may take place in business, nonprofit organizations and inf ...

based on a proposal by mathematician Charles Dodgson, better known as

Lewis Carroll Charles Lutwidge Dodgson (27 January 1832 – 14 January 1898), better known by his pen name Lewis Carroll, was an English author, poet, mathematician, photographer and reluctant Anglicanism, Anglican deacon. His most notable works are ''Alice ...

. The method searches for a

majority-preferred winner A Condorcet winner (, ) is a candidate who would receive the support of more than half of the electorate in a one-on-one race against any one of their opponents. Voting systems where a majority winner will always win are said to satisfy the Condo ...

; if no such winner is found, the method proceeds by finding the candidate who could be transformed into a Condorcet winner with the smallest number of ''ballot edits'' possible, where a ballot edit switches two neighboring candidates on a voter's ballot.

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 A Condorcet winner (, ) is a candidate who would receive the support of more than half of the electorate in a one-on-one race against any one of their opponents. Voting systems where a majority winner will always win are said to satisfy the Condo ...

Computation

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 In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

problem 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. by reduction from

Exact Cover In the mathematical field of combinatorics, given a collection \mathcal of subsets of a set X, an exact cover is a subcollection \mathcal^ of \mathcal such that each element in X is contained in ''exactly one'' subset in \mathcal^. One says that e ...

by 3-Sets (X3C). Given an integer ''k'' and an election, it is

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

to determine whether a candidate can become a Condorcet winner with fewer than ''k'' swaps.

References

Single-winner electoral systems Lewis Carroll {{election-stub