Dodgson's method is an

electoral system An electoral system or voting system is a set of rules that determine how elections and referendums are conducted and how their results are determined. Electoral systems are used in politics to elect governments, while non-political elections m ...

proposed by the author, mathematician and logician 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 and mathematician. His most notable works are '' Alice's Adventures in Wonderland'' (1865) and its sequ ...

. The method is to extend the

Condorcet method A Condorcet method (; ) is an election method that elects the candidate who wins a majority of the vote in every head-to-head election against each of the other candidates, that is, a candidate preferred by more voters than any others, whenever ...

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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

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 in each ballot (added over all candidates) before they become a

Condorcet winner An electoral system satisfies the Condorcet winner criterion () if it always chooses the Condorcet winner when one exists. The candidate who wins a majority of the vote in every head-to-head election against each of the other candidatesthat is, a ...

. In particular, if there is already a

, 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 In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

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 of subsets of a Set (mathematics), set , an exact cover is a subcollection of such that each element in is contained in ''exactly one'' subset in . In other words, is a partition ...

by 3-Sets (X3C).

References

Electoral systems Non-monotonic Condorcet methods Lewis Carroll {{election-stub