Dodgson's method: Difference between revisions
m
Clarify bubble sort metric
m (Add more criterion failures) |
m (Clarify bubble sort metric) |
||
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
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.
| |||