Dodgson's method: Difference between revisions
Psephomancy (talk | contribs) (Rename category) |
m (Fishburn's variant can be computed in polytime) |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Dodgson's method is a Condorcet method that ranks a candidate X according to the number of times adjacent candidates have to be swapped on a ballot (not necessarily the same ballot each time) to make X the Condorcet winner. The candidate with the least number of necessary swaps wins. |
|||
| ⚫ | |||
If X is the Condorcet winner, the number of swaps is zero, so the method passes Condorcet. However, determining the winner in the general case is complete for parallel access to NP,<ref>{{Cite journal|last=Hemaspaandra|first=Edith|last2=Hemaspaandra|first2=Lane A.|last3=Rothe|first3=Jörg|date=1997|editor-last=Degano|editor-first=Pierpaolo|editor2-last=Gorrieri|editor2-first=Roberto|editor3-last=Marchetti-Spaccamela|editor3-first=Alberto|title=Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP|url=https://arxiv.org/abs/cs/9907036|journal=Automata, Languages and Programming|series=Lecture Notes in Computer Science|language=en|location=Berlin, Heidelberg|publisher=Springer|volume=|pages=214–224|doi=10.1007/3-540-63165-8_179|isbn=978-3-540-69194-5|via=}}</ref> and thus NP-hard. |
|||
| ⚫ | |||
==Criterion compliances== |
|||
Dodgson's method passes the Condorcet criterion. It fails the [[independence of clones criterion]],<ref>{{Cite journal|last=Brandt|first=Felix|date=2009|title=Some Remarks on Dodgson's Voting Rule|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.149.5624&rep=rep1&type=pdf|journal=Mathematical Logic Quarterly|volume=55|issue=4|pages=460–463|doi=10.1002/malq.200810017|issn=1521-3870|via=}}</ref> the [[Smith criterion]], the [[monotonicity criterion]], and also fails the [[homogeneity criterion]]:<ref name="PCFishburn">{{Cite journal|last=Fishburn|first=Peter C.|date=1977-11-01|title=Condorcet Social Choice Functions|url=https://epubs.siam.org/doi/abs/10.1137/0133030|journal=SIAM Journal on Applied Mathematics|volume=33|issue=3|pages=477-479|doi=10.1137/0133030|issn=0036-1399|via=}}</ref> an election with 100 voters may return a different result to an election with 10 voters, even if the relative size of the factions is the same. |
|||
P. C. Fishburn proposed a variant that passes homogeneity<ref name="PCFishburn" /> and where the winner can be found in polynomial time,<ref>{{Cite journal|last=Rothe|first=Jörg|last2=Spakowski|first2=Holger|last3=Vogel|first3=Jörg|date=2003-08-01|title=Exact Complexity of the Winner Problem for Young Elections|url=https://arxiv.org/pdf/cs/0112021|journal=Theory of Computing Systems|language=en|volume=36|issue=4|pages=375–386|doi=10.1007/s00224-002-1093-z|issn=1433-0490|via=}}</ref> but the variant fails the other three criteria mentioned above. |
|||
==References== |
|||
<references /> |
|||
[[Category:Condorcet methods]] |
[[Category:Condorcet methods]] |
||
Latest revision as of 14:06, 25 August 2020
Dodgson's method is a Condorcet method that ranks a candidate X according to the number of times adjacent candidates have to be swapped on a ballot (not necessarily the same ballot each time) to make X the Condorcet winner. The candidate with the least number of necessary swaps wins.
If X is the Condorcet winner, the number of swaps is zero, so the method passes Condorcet. However, determining the winner in the general case is complete for parallel access to NP,[1] and thus NP-hard.
For more information, see Dodgson's method on Wikipedia.
Criterion compliances
Dodgson's method passes the Condorcet criterion. It fails the independence of clones criterion,[2] the Smith criterion, the monotonicity criterion, and also fails the homogeneity criterion:[3] an election with 100 voters may return a different result to an election with 10 voters, even if the relative size of the factions is the same.
P. C. Fishburn proposed a variant that passes homogeneity[3] and where the winner can be found in polynomial time,[4] but the variant fails the other three criteria mentioned above.
References
- ↑ Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg (1997). Degano, Pierpaolo; Gorrieri, Roberto; Marchetti-Spaccamela, Alberto (eds.). "Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP". Automata, Languages and Programming. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 214–224. doi:10.1007/3-540-63165-8_179. ISBN 978-3-540-69194-5.
- ↑ Brandt, Felix (2009). "Some Remarks on Dodgson's Voting Rule". Mathematical Logic Quarterly. 55 (4): 460–463. doi:10.1002/malq.200810017. ISSN 1521-3870.
- ↑ a b Fishburn, Peter C. (1977-11-01). "Condorcet Social Choice Functions". SIAM Journal on Applied Mathematics. 33 (3): 477–479. doi:10.1137/0133030. ISSN 0036-1399.
- ↑ Rothe, Jörg; Spakowski, Holger; Vogel, Jörg (2003-08-01). "Exact Complexity of the Winner Problem for Young Elections". Theory of Computing Systems. 36 (4): 375–386. doi:10.1007/s00224-002-1093-z. ISSN 1433-0490.