Schulze method: Difference between revisions
no edit summary
(→Notes) |
No edit summary |
||
Line 3:
The '''Schulze method''' is a [[voting system]] developed by Markus Schulze that selects a single winner using votes that express preferences. The Schulze method can also be used to create a sorted list of winners. The Schulze method is also known as "Schwartz sequential dropping" (SSD), "cloneproof Schwartz sequential dropping" (CSSD), "beatpath method", "beatpath winner", "path voting", and "path winner".
If there is a candidate who is preferred over the other candidates, when [[Pairwise counting|compared]] in turn with [[pairwise matchup|each of the others]], the Schulze method guarantees that that candidate will win. Because of this property, the Schulze method is (by definition) a [[Condorcet method]]. Note that this is different from some other preference voting systems such as [[Borda count|Borda]] and [[Instant-runoff voting]], which do not make this guarantee.
Many different heuristics for the Schulze method have been proposed. The most important heuristics are the path heuristic and the Schwartz set heuristic.
Line 496:
# If there are no defeats among the members of that set then they (plural in the case of a tie) win and the count ends.
# Otherwise, drop the weakest defeat among the candidates of that set. Go to 1.
To create a ranked list, simply remove the winner(s) of this procedure, and repeat it to find the 2nd place candidates, then 3rd place candidates, etc.
=== An Example ===
Line 675 ⟶ 677:
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.
=== Smith set-based variant ===
[[File:Smith based Schulze example.png|thumb|An example of the Smith set-based variation of the Schulze method.]]
A possible variation of Schulze (caution
Example (taken from https://en.wikipedia.org/wiki/User:MarkusSchulze/Wikimedia_Board_of_Trustees_elections,_2008):
In the Wikimedia Board of Trustees 2008 election, a [[Condorcet ranking]] of candidates existed from 1st to 5th place, and from 10th place to 15th place, but there was a [[Condorcet cycle]] from 6th place to 9th. The cycle can be seen as:
{| class="wikitable" style="text-align:center"
|-
!!![[m:User:Cimon Avaro|JH]]!![[m:User:Ryan Postlethwaite|RP]]!![[m:User:Sarcasticidealist|SS]]!![[m:User:Eclecticology|RS]]
|-
![[m:User:Cimon Avaro|Jussi-Ville Heiskanen]]
| ||bgcolor=#90ff90|841||bgcolor=#90ff90|798||bgcolor=#ff9090|737
|-
![[m:User:Ryan Postlethwaite|Ryan Postlethwaite]]
|bgcolor=#ff9090|770|| ||bgcolor=#90ff90|755||bgcolor=#90ff90|797
|-
![[m:User:Sarcasticidealist|Steve Smith]]
|bgcolor=#ff9090|750||bgcolor=#ff9090|744|| ||bgcolor=#90ff90|778
|-
![[m:User:Eclecticology|Ray Saintonge]]
|bgcolor=#90ff90|745||bgcolor=#ff9090|769||bgcolor=#ff9090|738||
|-
|}
To start off with, when looking at only these candidates, all of them are in the Smith set (because there is a [[beatpath]] cycle of SS>RS>JH>RP>SS).
If using winning votes to calculate defeat strength, then the defeats from weakest to strongest were: RS>JH:745, RP>SS:755, SS>RS:778, RP>RS:797, JH>SS:798, JH>RP:841.
The Smith set-based variant of Schulze (Smith-Schulze) would take the weakest defeat, RS>JH, and instead treat it as a victory for both RS and JH in that matchup. So now the new table is:
{| class="wikitable" style="text-align:center"
|-
!!![[m:User:Cimon Avaro|JH]]!![[m:User:Ryan Postlethwaite|RP]]!![[m:User:Sarcasticidealist|SS]]!![[m:User:Eclecticology|RS]]
|-
![[m:User:Cimon Avaro|Jussi-Ville Heiskanen]]
| ||bgcolor=#90ff90|841||bgcolor=#90ff90|798||bgcolor=#90ff90|737
|-
![[m:User:Ryan Postlethwaite|Ryan Postlethwaite]]
|bgcolor=#ff9090|770|| ||bgcolor=#90ff90|755||bgcolor=#90ff90|797
|-
![[m:User:Sarcasticidealist|Steve Smith]]
|bgcolor=#ff9090|750||bgcolor=#ff9090|744|| ||bgcolor=#90ff90|778
|-
![[m:User:Eclecticology|Ray Saintonge]]
|bgcolor=#90ff90|745||bgcolor=#ff9090|769||bgcolor=#ff9090|738||
|-
|}
The new Smith set is simply JH, since they pairwise beat all other candidates, so they are ranked uniquely highest among all of these candidates, and are thus put in 6th place in the overall Schulze ranking. To find the ranking of the remaining candidates, we remove JH, at which point the table becomes:
{| class="wikitable" style="text-align:center"
|-
!!![[m:User:Ryan Postlethwaite|RP]]!![[m:User:Sarcasticidealist|SS]]!![[m:User:Eclecticology|RS]]
|-
![[m:User:Ryan Postlethwaite|Ryan Postlethwaite]]
|| ||bgcolor=#90ff90|755||bgcolor=#90ff90|797
|-
![[m:User:Sarcasticidealist|Steve Smith]]
|||bgcolor=#ff9090|744|| ||bgcolor=#90ff90|778
|-
![[m:User:Eclecticology|Ray Saintonge]]
|||bgcolor=#ff9090|769||bgcolor=#ff9090|738
|-
|}
Here, there is a clear [[Condorcet ranking]] of these candidates of RP>SS>RS. Therefore, the Schulze ranking fills in the ranking from 6th place to 9th place as JH>RP>SS>RS.
== Use of the Schulze method ==
|