Schulze method: Difference between revisions
Add computational complexity section
No edit summary |
(Add computational complexity section) |
||
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 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.
| |||