Schulze method: Difference between revisions
m
Added clone independent category
No edit summary |
m (Added clone independent category) |
||
| (8 intermediate revisions by 4 users not shown) | |||
Line 635:
Using the [[first-past-the-post]] system and some other systems, Memphis would have won the election by having the most people, even though Nashville won every simulated pairwise election outright. Using [[Instant-runoff voting]] in this example would result in Knoxville winning, even though more people preferred Nashville over Knoxville.
== Satisfied
The Schulze method satisfies the following criteria:
Line 656:
# [[Summability criterion]]
# [[Strategic nomination|Independence of clones]]
# [[
#[[Independence of Smith-dominated Alternatives]]
Line 672:
The Schulze method was developed by Markus Schulze in 1997. The first time that the Schulze method was discussed in a public mailing list was in 1998 [http://lists.electorama.com/pipermail/election-methods-electorama.com/1998-July/001856.html] [http://lists.electorama.com/pipermail/election-methods-electorama.com/1998-August/001958.html] [http://lists.electorama.com/pipermail/election-methods-electorama.com/1998-August/002044.html] [http://lists.electorama.com/pipermail/election-methods-electorama.com/1998-September/002055.html] [http://lists.electorama.com/pipermail/election-methods-electorama.com/1998-November/002771.html]. In the following years, the Schulze method has been adopted e.g. by "Software in the Public Interest" (2003), Debian (2003), Gentoo (2005), TopCoder (2005), and "Sender Policy Framework" (2005). The first books on the Schulze method were written by Tideman (2006) and by Stahl and Johnson (2007).
== Computational complexity ==
== Notes ==▼
Using the Floyd-Warshall algorithm, determining the winner (or the order of finish of all candidates) takes <math>O(c^3)</math> time, where <math>c</math> is the number of candidates.
Unlike [[Ranked pairs]], determining the Schulze winner is in the NL complexity class. This indicates that it is easier to parallelize than [[Ranked pairs]] (unless NL=P).<ref>{{Cite journal|last=Csar|first=Theresa|last2=Lackner|first2=Martin|last3=Pichler|first3=Reinhard|date=2018-07|title=Computing the Schulze Method for Large-Scale Preference Data Sets|url=https://www.ijcai.org/proceedings/2018/25|journal=Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence|language=en|location=Stockholm, Sweden|publisher=International Joint Conferences on Artificial Intelligence Organization|pages=180–187|doi=10.24963/ijcai.2018/25|isbn=978-0-9992411-2-7}}</ref>
Because Schulze, like [[Ranked Pairs]], is equivalent to [[Minimax]] when there are 3 or fewer candidates with no pairwise ties, and passes [[Independence of Smith-dominated Alternatives]], it is possible to eliminate all candidates not in the Smith set before running Schulze and get the same result, potentially making computation easier, and when the Smith set has 3 or fewer members with no pairwise ties between them, Minimax can then be used instead after eliminating non-Smith candidates to find the Schulze winner. ▼
▲Because Schulze, like [[Ranked Pairs]], is equivalent to [[Minimax]] when there are 3 or fewer candidates with no pairwise ties, and passes [[Independence of Smith-dominated Alternatives]], it is possible to eliminate all candidates not in the Smith set before running Schulze and get the same result, potentially making computation easier, and when the Smith set has 3 or fewer members with no pairwise ties between them, Minimax can then be used instead after eliminating non-Smith candidates to find the Schulze winner.
▲== Notes ==
The Schulze ranking is a [[Smith set ranking]]. This is because every candidate in the n-th Smith set will have a beatpath to all candidates in lower Smith sets (because they directly pairwise beat them), but all candidates in lower Smith sets will have no beatpath back to the candidates in the n-th Smith set, because by definition the candidates in the lower Smith sets are pairwise beaten by all candidates in higher Smith sets, and can thus only pairwise beat fellow members of lower Smith sets, who are also all pairwise beaten by all candidates in the n-th Smith set. Therefore, the strength of the path for candidates in the n-th Smith set to candidates in lower Smith sets is always stronger than the other way around. The same logic demonstrates why all candidates in the n-th Smith set will be ranked lower than all candidates in higher Smith sets.
Line 883 ⟶ 888:
* [http://m-schulze.9mail.de/serie3_9-10.pdf Schulze-Methode] by the University of Stuttgart
===
:''<span id="Advocacy">formerly "Advocacy"</span>''
This section contains various public discussions about the Schulze method.
==== 2020 ====
* [https://www.reddit.com/r/EndFPTP/comments/gwik8c/what_are_the_key_disadvantages_of_the_schulze/ "What are the key disadvantages of the Schulze method?" (2020-06-04)] - a discussion started on [[EndFPTP]] regarding the possible disadvantages of Schulze's method.
==== 2019 and earlier ====
<!-- this section contains a lot of links; please try to keep it organized by the author's last name. -->
* [http://fc.antioch.edu/~james_green-armytage/vm/survey.htm#beatpath Voting Methods Survey] by James Green-Armytage
* [https://www.
* [http://accuratedemocracy.com/voting_rules.htm Accurate Democracy] by Rob Loring
* [http://rangevoting.org/SchulzeExplan.html Schulze beatpaths method] by Warren D. Smith
Line 893 ⟶ 905:
* [http://seehuhn.de/comp/vote.html The Debian Voting System] by Jochen Voss
* [http://lists.electorama.com/pipermail/election-methods-electorama.com/ election-methods: a mailing list containing technical discussions about election methods]
* [https://politics.stackexchange.com/questions/15637/why-is-schulze-the-most-popular-condorcet-election-method "Why is Schulze the most popular Condorcet election method?"] ''[[politics.stackexchange.com]]'' 2017-02-14
=== Research papers ===
Line 946 ⟶ 959:
[[Category:Smith-efficient Condorcet methods]]
[[Category:Defeat-dropping Condorcet methods]]
[[Category:Monotonic_electoral_systems]]
[[Category:Ranked voting methods]]
[[Category:Clone-independent electoral systems]]
| |||