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.

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]

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. S2CID 154114517. 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. ISBN 9780716710455.

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

[btt-1] 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. S2CID 154114517. 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.

[gj1979-2] Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability. W.H. Freeman Co., San Francisco. ISBN 9780716710455.