Dodgson's method
In this article, we will thoroughly explore the phenomenon of Dodgson's method and its implications in modern society. From its origins to its impact today, we will delve into all facets of this issue, analyzing its causes, consequences and possible solutions. Along the following lines, we will examine different perspectives and opinions on Dodgson's method, with the aim of offering a complete and objective overview of this issue. This article will serve as an informative and thoughtful guide for all those interested in better understanding Dodgson's method and its influence on our environment.
| A joint Politics and Economics series |
| Social choice and electoral systems |
|---|
 |
 Mathematics portal |
Dodgson's method is an electoral system based on a proposal by mathematician Charles Dodgson, better known as Lewis Carroll. The method searches for a majority-preferred winner; 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.[1]
This classic Condorcet-consistent system, though computationally complex, was defined in Dodgson's A Method of Taking Votes on More an Two Issues pamphlet. It appeared in March 1876, printed by the Clarendon Press, Oxford and headed “not yet published”.[2][3]
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.
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 problem[4] by reduction from Exact Cover by 3-Sets (X3C).[5]
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.
References
- ^ Ratliff, Thomas C. (2001-01-01). "A comparison of Dodgson's method and Kemeny's rule". Social Choice and Welfare. 18 (1): 79–89. doi:10.1007/s003550000060. ISSN 1432-217X.
- ^ Mclean, Iain. "Voting". The Mathematical World of Charles L. Dodgson (Lewis Carroll). Chapter 5.
- ^ Caragiannis, Ioannis. "Dodgson's Rule and Young's Rule" (PDF). Handbook of Computational Social Choice.
- ^ 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 election-related article is a stub. You can help Wikipedia by expanding it. |