Schulze method: Difference between revisions

From electowiki
Content added Content deleted
VisualWikitext
imported>MarkusSchulze
m (Added clone independent category)
 
(46 intermediate revisions by 13 users not shown)
Line 1: Line 1:
{{Wikipedia}}

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".
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 compared in turn with 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.
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.
Many different heuristics for the Schulze method have been proposed. The most important heuristics are the path heuristic and the Schwartz set heuristic.
Line 19: Line 21:
:# For all i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
:# For all i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
:# For all i = 1,...,(n-1): d[C(i),C(i+1)] ≥ p.
:# For all i = 1,...,(n-1): d[C(i),C(i+1)] ≥ p.
:# For at least one i = 1,...,(n-1): d[C(i),C(i+1)] = p.


p[A,B], the ''strength of the strongest path'' from candidate A to candidate B, is the maximum value such that there is a path from candidate A to candidate B of that strength. If there is no path from candidate A to candidate B at all, then p[A,B] : = 0.
p[A,B], the ''strength of the strongest path'' from candidate A to candidate B, is the maximum value such that there is a path from candidate A to candidate B of that strength. If there is no path from candidate A to candidate B at all, then p[A,B] : = 0.
Line 26: Line 27:


Candidate D is a ''potential winner'' if and only if p[D,E] ≥ p[E,D] for every other candidate E.
Candidate D is a ''potential winner'' if and only if p[D,E] ≥ p[E,D] for every other candidate E.

=== Remark ===

It is possible to prove that p[X,Y] > p[Y,X] and p[Y,Z] > p[Z,Y] together imply p[X,Z] > p[Z,X]. Therefore, it is guaranteed (1) that the above definition of "''better''" really defines a transitive relation and (2) that there is always at least one candidate D with p[D,E] ≥ p[E,D] for every other candidate E.


=== Implementation ===
=== Implementation ===
Line 176: Line 181:


Candidate E is a potential winner, because p[E,X] ≥ p[X,E] for every other candidate X.
Candidate E is a potential winner, because p[E,X] ≥ p[X,E] for every other candidate X.

As 25 = p[E,A] > p[A,E] = 24, candidate E is ''better'' than candidate A.

As 28 = p[E,B] > p[B,E] = 24, candidate E is ''better'' than candidate B.

As 28 = p[E,C] > p[C,E] = 24, candidate E is ''better'' than candidate C.

As 31 = p[E,D] > p[D,E] = 24, candidate E is ''better'' than candidate D.

As 28 = p[A,B] > p[B,A] = 25, candidate A is ''better'' than candidate B.

As 28 = p[A,C] > p[C,A] = 25, candidate A is ''better'' than candidate C.

As 30 = p[A,D] > p[D,A] = 25, candidate A is ''better'' than candidate D.

As 29 = p[C,B] > p[B,C] = 28, candidate C is ''better'' than candidate B.

As 29 = p[C,D] > p[D,C] = 28, candidate C is ''better'' than candidate D.

As 33 = p[B,D] > p[D,B] = 28, candidate B is ''better'' than candidate D.

Therefore, the Schulze ranking is E > A > C > B > D.


==== Example 2 ====
==== Example 2 ====
Line 251: Line 278:


Candidate D is a potential winner, because p[D,X] ≥ p[X,D] for every other candidate X.
Candidate D is a potential winner, because p[D,X] ≥ p[X,D] for every other candidate X.

As 18 = p[D,A] > p[A,D] = 17, candidate D is ''better'' than candidate A.

As 18 = p[D,B] > p[B,D] = 17, candidate D is ''better'' than candidate B.

As 18 = p[D,C] > p[C,D] = 17, candidate D is ''better'' than candidate C.

As 20 = p[A,B] > p[B,A] = 19, candidate A is ''better'' than candidate B.

As 20 = p[A,C] > p[C,A] = 19, candidate A is ''better'' than candidate C.

As 21 = p[C,B] > p[B,C] = 19, candidate C is ''better'' than candidate B.

Therefore, the Schulze ranking is D > A > C > B.


==== Example 3 ====
==== Example 3 ====
Line 335: Line 376:


Candidate B is a potential winner, because p[B,X] ≥ p[X,B] for every other candidate X.
Candidate B is a potential winner, because p[B,X] ≥ p[X,B] for every other candidate X.

As 19 = p[B,A] > p[A,B] = 18, candidate B is ''better'' than candidate A.

As 19 = p[B,C] > p[C,B] = 18, candidate B is ''better'' than candidate C.

As 19 = p[B,D] > p[D,B] = 18, candidate B is ''better'' than candidate D.

As 19 = p[B,E] > p[E,B] = 18, candidate B is ''better'' than candidate E.

As 20 = p[A,C] > p[C,A] = 19, candidate A is ''better'' than candidate C.

As 21 = p[A,D] > p[D,A] = 19, candidate A is ''better'' than candidate D.

As 21 = p[A,E] > p[E,A] = 19, candidate A is ''better'' than candidate E.

As 20 = p[D,C] > p[C,D] = 19, candidate D is ''better'' than candidate C.

As 30 = p[D,E] > p[E,D] = 19, candidate D is ''better'' than candidate E.

As 20 = p[E,C] > p[C,E] = 19, candidate E is ''better'' than candidate C.

Therefore, the Schulze ranking is B > A > D > E > C.


==== Example 4 ====
==== Example 4 ====
Line 405: Line 468:


Candidate B and candidate D are potential winners, because p[B,X] ≥ p[X,B] for every other candidate X and p[D,Y] ≥ p[Y,D] for every other candidate Y.
Candidate B and candidate D are potential winners, because p[B,X] ≥ p[X,B] for every other candidate X and p[D,Y] ≥ p[Y,D] for every other candidate Y.

As 7 = p[B,C] > p[C,B] = 5, candidate B is ''better'' than candidate C.

As 6 = p[D,A] > p[A,D] = 5, candidate D is ''better'' than candidate A.

Possible Schulze rankings are B > C > D > A, B > D > A > C, B > D > C > A, D > A > B > C, D > B > A > C, and D > B > C > A.


== The Schwartz set heuristic ==
== The Schwartz set heuristic ==
Line 427: 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.
# 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.
# 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 ===
=== An Example ===
Line 443: Line 514:
Let's say that in the vote, the voters vote based on geographic proximity. Assuming that the population distribution of the rest of Tennessee follows from those population centers, one could easily envision an election where the percentages of votes would be as follows:
Let's say that in the vote, the voters vote based on geographic proximity. Assuming that the population distribution of the rest of Tennessee follows from those population centers, one could easily envision an election where the percentages of votes would be as follows:


<table border=1>
<table class="wikitable" border="1">
<tr>
<tr>
<td>
<td>
Line 551: Line 622:
The Schulze method then says to drop the weakest defeat, so we drop C > A and are left with
The Schulze method then says to drop the weakest defeat, so we drop C > A and are left with


* A > B 72% (as C has been removed)
* A > B 72% (as C has been removed from the Schwartz set and thus eliminated, since they no longer beat or tie anyone in the set)


Therefore, A is the winner.
Therefore, A is the winner.
Line 564: 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.
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 Criteria ==
== Satisfied criteria ==


The Schulze method satisfies the following criteria:
The Schulze method satisfies the following criteria:
Line 585: Line 656:
# [[Summability criterion]]
# [[Summability criterion]]
# [[Strategic nomination|Independence of clones]]
# [[Strategic nomination|Independence of clones]]
# [[Neutrality of Spoiled Ballots]]
# [[Blank Ballot Criterion]]
#[[Independence of Smith-dominated Alternatives]]


The Schulze method violates the following criteria:
The Schulze method violates the following criteria:
Line 599: Line 671:


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).
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 ==
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.

== 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.

=== 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: not proposed, endorsed, or seriously analyzed by Markus Schulze) which is only [[Smith-efficient]] and not Schwartz-efficient (see the image to the right for an example) can be described as "Iteratively repeat the following two steps until there are no more pairwise defeats, at which point all of the remaining candidates are tied to win: 1) Eliminate all candidates not in the [[Smith set]], and then 2) turn the weakest pairwise defeat into a [[pairwise beat|pairwise victory]] for both candidates in the matchup." This can be argued to be simpler than regular Schulze, since the Smith set is easier to understand than the Schwartz set. It will return the same result as regular Schulze when there are no pairwise ties between any members of the Smith set. This variation could be called the '''cloneproof Smith sequential dropping method''' (though when dropping defeats, they are "flipped" to victories for both candidates in the matchup, rather than turned into a pairwise tie). It may be possible when using this variation to pretend a particular pairwise matchup simply didn't happen, rather than to say that both candidates in the matchup got a pairwise victory, when dropping defeats.

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 ==
== Use of the Schulze method ==
Line 606: Line 758:
* [http://www.annodex.org/ Annodex Association] [http://www.cs.cornell.edu/w8/~andru/cgi-perl/civs/results.pl?id=E_50cfc592ae8f13d9]
* [http://www.annodex.org/ Annodex Association] [http://www.cs.cornell.edu/w8/~andru/cgi-perl/civs/results.pl?id=E_50cfc592ae8f13d9]
* [http://blitzed.org/ Blitzed] [http://wiki.blitzed.org/Condorcet_method_for_admin_voting]
* [http://blitzed.org/ Blitzed] [http://wiki.blitzed.org/Condorcet_method_for_admin_voting]
* [http://www.boardgamegeek.com/ BoardGameGeek] [http://www.boardgamegeek.com/article/1751580] [http://www.boardgamegeek.com/article/2582330] [http://www.boardgamegeek.com/article/2674153]
* [http://www.boardgamegeek.com/ BoardGameGeek] [http://www.boardgamegeek.com/article/1751580] [http://www.boardgamegeek.com/article/2582330] [http://www.boardgamegeek.com/article/2674153] [http://www.boardgamegeek.com/article/3840078]
* [http://incubator.apache.org/cassandra/ Cassandra] [http://article.gmane.org/gmane.comp.db.cassandra.devel/424/match=condorcet+schwartz+sequential+dropping+beatpath]
* [http://www.heroinewarrior.com/cinelerra.php Cinelerra] [http://www.cs.cornell.edu/w8/~andru/cgi-perl/civs/results.pl?id=E_7df51370797b45d6]
* [http://0xAA.org Codex Alpe Adria] [http://0xAA.org/competitions/]
* [http://0xAA.org Codex Alpe Adria] [http://0xAA.org/competitions/]
* [http://www.marine.usf.edu/ College of Marine Science] [http://www.marine.usf.edu/fellowships/Guidelines-and-Application-2009-2010.pdf]
* [http://www.marine.usf.edu/ College of Marine Science] [http://www.marine.usf.edu/fellowships/Guidelines-and-Application-2009-2010.pdf]
Line 614: Line 768:
* [http://nw.dfey.org/wiki/Main_Page Digital Freedom in Education and Youth] [http://nw.dfey.org/wiki/Logo_Competition#Voting_Timeline]
* [http://nw.dfey.org/wiki/Main_Page Digital Freedom in Education and Youth] [http://nw.dfey.org/wiki/Logo_Competition#Voting_Timeline]
* [http://enmasse.ca/index.php EnMasse Forums]
* [http://enmasse.ca/index.php EnMasse Forums]
* [http://en.eurobilltracker.com/ EuroBillTracker] [http://forum.eurobilltracker.eu/viewtopic.php?t=4920&highlight=condorcet+beatpath+ssd] [http://forum.eurobilltracker.eu/viewtopic.php?t=4921&highlight=condorcet] [http://forum.eurobilltracker.eu/viewtopic.php?t=9353&highlight=condorcet+beatpath] [http://forum.eurobilltracker.eu/viewtopic.php?t=10564&highlight=condorcet+beatpath]
* [http://en.eurobilltracker.com/ EuroBillTracker] [http://forum.eurobilltracker.eu/viewtopic.php?t=4920&highlight=condorcet+beatpath+ssd] [http://forum.eurobilltracker.eu/viewtopic.php?t=4921&highlight=condorcet] [http://forum.eurobilltracker.eu/viewtopic.php?t=9353&highlight=condorcet+beatpath] [http://forum.eurobilltracker.eu/viewtopic.php?t=10564&highlight=condorcet+beatpath] [http://forum.eurobilltracker.com/viewtopic.php?f=26&t=17919&start=15#p714947]
* [http://www.eudec.org/ European Democratic Education Conference] [http://www.eudec.org/forum/index.php?topic=96.msg352#msg352]
* [http://www.eudec.org/ European Democratic Education Conference] [http://www.eudec.org/forum/index.php?topic=96.msg352#msg352]
* [http://fairtradenorthwest.org/ Fair Trade Northwest] (see article XI section 2 of their [http://fairtradenorthwest.org/FTNW%20Bylaws.pdf bylaws])
* [http://fairtradenorthwest.org/ Fair Trade Northwest] (see article XI section 2 of their [http://fairtradenorthwest.org/FTNW%20Bylaws.pdf bylaws])
Line 622: Line 776:
* [http://www.gentoo.org/ Gentoo Foundation] [http://www.gentoo.org/foundation/en/] [http://article.gmane.org/gmane.linux.gentoo.nfp/252/match=Condorcet+Schwartz+drop+dropped] [http://article.gmane.org/gmane.linux.gentoo.weekly-news/121/match=Condorcet] [http://article.gmane.org/gmane.linux.gentoo.devel/28603/match=Condorcet+Cloneproof+Schwartz+Sequential+Dropping] [http://article.gmane.org/gmane.linux.gentoo.devel/42260/match=Schulze+method] [http://dev.gentoo.org/~fox2mike/elections/council/2007/council2007-results]
* [http://www.gentoo.org/ Gentoo Foundation] [http://www.gentoo.org/foundation/en/] [http://article.gmane.org/gmane.linux.gentoo.nfp/252/match=Condorcet+Schwartz+drop+dropped] [http://article.gmane.org/gmane.linux.gentoo.weekly-news/121/match=Condorcet] [http://article.gmane.org/gmane.linux.gentoo.devel/28603/match=Condorcet+Cloneproof+Schwartz+Sequential+Dropping] [http://article.gmane.org/gmane.linux.gentoo.devel/42260/match=Schulze+method] [http://dev.gentoo.org/~fox2mike/elections/council/2007/council2007-results]
* [http://www.gnupg.org/ GNU Privacy Guard (GnuPG)] [http://logo-contest.gnupg.org/results.html]
* [http://www.gnupg.org/ GNU Privacy Guard (GnuPG)] [http://logo-contest.gnupg.org/results.html]
* [http://gbg.hackerspace.se/site/ Gothenburg Hacker Space (GHS)] (see §14 of the [http://gbg.hackerspace.se/site/om-ghs/stadgar/ bylaws])
* [http://gso.cs.binghamton.edu/index.php/GSOCS_Home Graduate Student Organization at the State University of New York: Computer Science (GSOCS)] [http://gso.cs.binghamton.edu/index.php/Voting]
* [http://gso.cs.binghamton.edu/index.php/GSOCS_Home Graduate Student Organization at the State University of New York: Computer Science (GSOCS)] [http://gso.cs.binghamton.edu/index.php/Voting]
* [http://haskell.org/ Haskell] [http://www.cs.cornell.edu/w8/~andru/cgi-perl/civs/results.pl?num_winners=1&id=E_d21b0256a4fd5ed7&algorithm=beatpath]
* [http://haskell.org/ Haskell] [http://www.cs.cornell.edu/w8/~andru/cgi-perl/civs/results.pl?num_winners=1&id=E_d21b0256a4fd5ed7&algorithm=beatpath]
Line 627: Line 782:
* [http://www.kde.org/ KDE e.V.] (see section 3.4.1 of the [http://ev.kde.org/rules/online_voting.php Rules of Procedures for Online Voting])
* [http://www.kde.org/ KDE e.V.] (see section 3.4.1 of the [http://ev.kde.org/rules/online_voting.php Rules of Procedures for Online Voting])
* [http://kingmanhall.org/ Kingman Hall] [http://www.livejournal.com/users/zestyping/102718.html] [http://www.livejournal.com/users/zestyping/111588.html]
* [http://kingmanhall.org/ Kingman Hall] [http://www.livejournal.com/users/zestyping/102718.html] [http://www.livejournal.com/users/zestyping/111588.html]
* [http://www.knightfdn.org/ Knight Foundation] [http://civic.mit.edu/blog/andrew/knight-foundation-awards-5000-to-best-created-on-the-spot-projects] [http://selectricity.org:3000/voter/results/open.993]
* [http://www.knightfdn.org/ Knight Foundation] [http://civic.mit.edu/blog/andrew/knight-foundation-awards-5000-to-best-created-on-the-spot-projects]
* [http://www.kumoricon.org/ Kumoricon] [http://www.kumoricon.org/forums/index.php?topic=2599.45] [http://www.kumoricon.org/forums/index.php?topic=4497.0] [http://www.kumoricon.org/forums/index.php?topic=6653.0] [http://www.kumoricon.org/forums/index.php?topic=10048.0]
* [http://www.kumoricon.org/ Kumoricon] [http://www.kumoricon.org/forums/index.php?topic=2599.45] [http://www.kumoricon.org/forums/index.php?topic=4497.0] [http://www.kumoricon.org/forums/index.php?topic=6653.0] [http://www.kumoricon.org/forums/index.php?topic=10048.0]
* [http://www.lopsa.org/ League of Professional System Administrators (LOPSA)] (see article 8.3 of the [http://governance.lopsa.org/index.php/LOPSA_Bylaws bylaws])
* [http://www.libre-entreprise.org/ Libre-Entreprise] [http://www.libre-entreprise.org/index.php/Election:DateReunionSolutionLinux2006] [http://www.libre-entreprise.org/index.php/Election:EntreeLibricks]
* [http://www.apollonic.info/ Mason Apollonic Society] (see article 5 of the [http://www.apollonic.info/Constitution.pdf constitution])
* [http://www.mkm-ig.org/ Mathematical Knowledge Management Interest Group (MKM-IG)] (The MKM-IG uses [http://condorcet-dd.sourceforge.net/ Condorcet with dual dropping]. That means: The Schulze ranking and the [[Ranked Pairs|ranked pairs]] ranking are calculated and the winner is the top-ranked candidate of that of these two rankings that has the better Kemeny score.) [http://www.mkm-ig.org/charter.html] [http://lists.jacobs-university.de/pipermail/projects-mkm-ig/2004-November/000041.html] [http://lists.jacobs-university.de/pipermail/projects-mkm-ig/2005-December/000072.html] [http://lists.jacobs-university.de/pipermail/projects-mkm-ig/2007-August/000406.html]
* [http://www.mkm-ig.org/ Mathematical Knowledge Management Interest Group (MKM-IG)] (The MKM-IG uses [http://condorcet-dd.sourceforge.net/ Condorcet with dual dropping]. That means: The Schulze ranking and the [[Ranked Pairs|ranked pairs]] ranking are calculated and the winner is the top-ranked candidate of that of these two rankings that has the better Kemeny score.) [http://www.mkm-ig.org/charter.html] [http://lists.jacobs-university.de/pipermail/projects-mkm-ig/2004-November/000041.html] [http://lists.jacobs-university.de/pipermail/projects-mkm-ig/2005-December/000072.html] [http://lists.jacobs-university.de/pipermail/projects-mkm-ig/2007-August/000406.html]
* [http://metalab.at/ Metalab] [http://metalab.at/wiki/Generalversammlung_2007/Wahlmodus]
* [http://metalab.at/ Metalab] [http://metalab.at/wiki/Generalversammlung_2007/Wahlmodus]
* [http://www.mtv.com/ Music Television (MTV)] [http://en.oreilly.com/oscon2008/public/schedule/detail/3230]
* [http://www.mtv.com/ Music Television (MTV)] [http://en.oreilly.com/oscon2008/public/schedule/detail/3230]
* [http://netznetz.net/ netznetz] [http://netznetz.net/wiki/index.php?title=Online-Abstimmung&oldid=3867#Wahl_Auswertung] [http://netznetz.net/wiki/index.php?title=Verfassungsentwurf&oldid=3896#Abstimmungsmodus]
* [https://www.noisebridge.net/ Noisebridge] [https://www.noisebridge.net/index.php?title=2009_Director_Elections&oldid=8778]
* [http://www.nscyc.org/home North Shore Cyclists (NSC)] [http://www.nscyc.org/JerseyWinner] [http://www.cs.cornell.edu/w8/~andru/cgi-perl/civs/results.pl?id=E_6c53f2bddb068673]
* [http://www.nscyc.org/home North Shore Cyclists (NSC)] [http://www.nscyc.org/JerseyWinner] [http://www.cs.cornell.edu/w8/~andru/cgi-perl/civs/results.pl?id=E_6c53f2bddb068673]
* [http://www.opencouchsurfing.org/ OpenCouchSurfing] [http://groups.google.com/group/open-couchsurfing/msg/fe5a2edf9e82931c]
* [http://www.opencouchsurfing.org/ OpenCouchSurfing] [http://groups.google.com/group/open-couchsurfing/msg/fe5a2edf9e82931c]
* [http://www.parkscholars.org/index.php Park Alumni Society (PAS)] [http://www.parkscholars.org/voting.php]
* [http://www.piratpartiet.se/ Pirate Party of Sweden] [http://forum.piratpartiet.se/FindPost174988.aspx] [http://forum.piratpartiet.se/FindPost176567.aspx]
* [http://www.pittsburgh-ultimate.org/ Pittsburgh Ultimate] [http://www.cs.cornell.edu/w8/~andru/cgi-perl/civs/results.pl?id=E_89773564141f0859]
* [http://www.pittsburgh-ultimate.org/ Pittsburgh Ultimate] [http://www.cs.cornell.edu/w8/~andru/cgi-perl/civs/results.pl?id=E_89773564141f0859]
* [http://rpmrepo.org/ RPMrepo] [http://rpmrepo.org/driesverachtert/LogoVoting]
* [http://rpmrepo.org/ RPMrepo] [http://rpmrepo.org/driesverachtert/LogoVoting]
Line 639: Line 801:
* [http://www.spi-inc.org/ Software in the Public Interest (SPI)] [http://www.spi-inc.org/corporate/resolutions/2003-01-06-wta.1]
* [http://www.spi-inc.org/ Software in the Public Interest (SPI)] [http://www.spi-inc.org/corporate/resolutions/2003-01-06-wta.1]
* [http://freeculture.org/ Students for Free Culture] [http://wiki.freeculture.org/Bylaws] [http://blog.selectricity.org/?p=4]
* [http://freeculture.org/ Students for Free Culture] [http://wiki.freeculture.org/Bylaws] [http://blog.selectricity.org/?p=4]
* [http://www.sugarlabs.org/ Sugar Labs] [http://lists.sugarlabs.org/archive/iaep/2009-September/008620.html]
* [http://www.topcoder.com/ TopCoder] [http://www.topcoder.com/tc?module=Static&d1=tournaments&d2=tco06&d3=logo_rules] [http://www.topcoder.com/tc?module=Static&d1=tournaments&d2=tccc06&d3=logo_rules] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2030] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2046] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2047] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2050] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2122] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2127] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2133] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2183]
* [http://www.topcoder.com/ TopCoder] [http://www.topcoder.com/tc?module=Static&d1=tournaments&d2=tco06&d3=logo_rules] [http://www.topcoder.com/tc?module=Static&d1=tournaments&d2=tccc06&d3=logo_rules] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2030] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2046] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2047] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2050] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2122] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2127] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2133] [http://studio.topcoder.com/?module=ViewContestDetails&ct=2183]
* [http://www.ubuntu.com/ Ubuntu] [http://www.cs.cornell.edu/w8/~andru/cgi-perl/civs/results.pl?id=E_e09bf9bea196cfff]
* [http://wikimediafoundation.org/ Wikimedia Foundation] [http://lists.wikimedia.org/pipermail/foundation-l/2008-May/043134.html]
* [http://wikimediafoundation.org/ Wikimedia Foundation] [http://lists.wikimedia.org/pipermail/foundation-l/2008-May/043134.html] [http://lists.wikimedia.org/pipermail/foundation-l/2008-June/044361.html] [http://meta.wikimedia.org/wiki/Board_elections/2008/Results] [http://meta.wikimedia.org/wiki/Board_elections/2009/Results]
* [http://fr.wikipedia.org/wiki/Wikip%C3%A9dia Wikipedia in French] (The Schulze method is one of three methods recommended for decision-making.) [http://fr.wikipedia.org/wiki/Wikip%C3%A9dia:Prise_de_d%C3%A9cision/Choix_dans_les_votes]
* [http://fr.wikipedia.org/wiki/Wikip%C3%A9dia Wikipedia in French] (The Schulze method is one of three methods recommended for decision-making.) [http://fr.wikipedia.org/wiki/Wikip%C3%A9dia:Prise_de_d%C3%A9cision/Choix_dans_les_votes]
* [http://he.wikipedia.org/wiki/%D7%A2%D7%9E%D7%95%D7%93_%D7%A8%D7%90%D7%A9%D7%99 Wikipedia in Hebrew] [http://he.wikipedia.org/w/index.php?title=ויקיפדיה:פרלמנט&oldid=7014412#.D7.94.D7.A7.D7.93.D7.9E.D7.94]
* [http://hu.wikipedia.org/wiki/Wikip%C3%A9dia Wikipedia in Hungarian] [http://hu.wikipedia.org/wiki/Wikip%C3%A9dia:Szavaz%C3%A1s/Az_%E2%80%9EArbitr%C3%A1ci%C3%B3s_Bizotts%C3%A1g%E2%80%9D_magyar_neve] [http://hu.wikipedia.org/wiki/Sablon_vita:F%C5%91/Szavaz%C3%A1s]
* [http://hu.wikipedia.org/wiki/Wikip%C3%A9dia Wikipedia in Hungarian] [http://hu.wikipedia.org/wiki/Wikip%C3%A9dia:Szavaz%C3%A1s/Az_%E2%80%9EArbitr%C3%A1ci%C3%B3s_Bizotts%C3%A1g%E2%80%9D_magyar_neve] [http://hu.wikipedia.org/wiki/Sablon_vita:F%C5%91/Szavaz%C3%A1s]
* [http://ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F Wikipedia in Russian] [http://toolserver.org/~kalan/arb7/schulze] [http://toolserver.org/~kalan/arb8/schulze] [http://ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%92%D1%8B%D0%B1%D0%BE%D1%80%D1%8B_%D0%B0%D1%80%D0%B1%D0%B8%D1%82%D1%80%D0%BE%D0%B2/%D0%92%D0%B5%D1%81%D0%BD%D0%B0_2009]
* [http://es.wikipedia.org/wiki/Wikipedia Wikipedia in Spanish] [http://es.wikipedia.org/wiki/Wikipedia_Discusi%C3%B3n:Comit%C3%A9_de_Resoluci%C3%B3n_de_Conflictos/Archivo1#Opci.C3.B3n_2:_m.C3.A9todo_Schulze]
* [http://es.wikipedia.org/wiki/Wikipedia Wikipedia in Spanish] [http://es.wikipedia.org/wiki/Wikipedia_Discusi%C3%B3n:Comit%C3%A9_de_Resoluci%C3%B3n_de_Conflictos/Archivo1#Opci.C3.B3n_2:_m.C3.A9todo_Schulze]

=== Wikimedia Foundation, 2008 ===
{{Merge to|Category:Schulze method elections|date=August 2019}}
In June 2008, the Wikimedia Foundation used the Schulze method for the election to its Board of Trustees: One vacant seat had to be filled. There were 15 candidates, about 26,000 eligible voters, and 3,019 valid ballots.

As [http://meta.wikimedia.org/wiki/User:Wing Chen] was a clear Condorcet winner, he won the vacant seat. However, there was a tie for sixth to ninth position between [http://meta.wikimedia.org/wiki/User:Cimon_Avaro Heiskanen], [http://meta.wikimedia.org/wiki/User:Ryan_Postlethwaite Postlethwaite], [http://meta.wikimedia.org/wiki/User:Sarcasticidealist Smith], and [http://meta.wikimedia.org/wiki/User:Eclecticology Saintonge]. [http://meta.wikimedia.org/wiki/User:Cimon_Avaro Heiskanen] beat [http://meta.wikimedia.org/wiki/User:Ryan_Postlethwaite Postlethwaite]; [http://meta.wikimedia.org/wiki/User:Ryan_Postlethwaite Postlethwaite] beat [http://meta.wikimedia.org/wiki/User:Sarcasticidealist Smith]; [http://meta.wikimedia.org/wiki/User:Sarcasticidealist Smith] beat [http://meta.wikimedia.org/wiki/User:Eclecticology Saintonge]; [http://meta.wikimedia.org/wiki/User:Eclecticology Saintonge] beat [http://meta.wikimedia.org/wiki/User:Cimon_Avaro Heiskanen].

{| class="wikitable" style="text-align:center" border="2"
|-
! !![http://meta.wikimedia.org/wiki/User:Wing TC]!![http://meta.wikimedia.org/wiki/User:Alex_Bakharev AB]!![http://meta.wikimedia.org/wiki/User:Sj SK]!![http://meta.wikimedia.org/wiki/User:Harel HC]!![http://meta.wikimedia.org/wiki/User:Dedalus AH]!![http://meta.wikimedia.org/wiki/User:Cimon_Avaro JH]!![http://meta.wikimedia.org/wiki/User:Ryan_Postlethwaite RP]!![http://meta.wikimedia.org/wiki/User:Sarcasticidealist SS]!![http://meta.wikimedia.org/wiki/User:Eclecticology RS]!![http://meta.wikimedia.org/wiki/User:Swatjester DR]!![http://meta.wikimedia.org/wiki/User:Cspurrier CS]!![http://meta.wikimedia.org/wiki/User:MBisanz MB]!![http://meta.wikimedia.org/wiki/User:Kmweber KW]!![http://meta.wikimedia.org/wiki/User:Skenmy PW]!![http://meta.wikimedia.org/wiki/User:Thekohser GK]
|-
![http://meta.wikimedia.org/wiki/User:Wing Ting Chen]
| ||bgcolor=#90ff90|1086||bgcolor=#90ff90|1044||bgcolor=#90ff90|1108||bgcolor=#90ff90|1135||bgcolor=#90ff90|1151||bgcolor=#90ff90|1245||bgcolor=#90ff90|1190||bgcolor=#90ff90|1182||bgcolor=#90ff90|1248||bgcolor=#90ff90|1263||bgcolor=#90ff90|1306||bgcolor=#90ff90|1344||bgcolor=#90ff90|1354||bgcolor=#90ff90|1421
|-
![http://meta.wikimedia.org/wiki/User:Alex_Bakharev Alex Bakharev]
|bgcolor=#ff9090|844|| ||bgcolor=#90ff90|932||bgcolor=#90ff90|984||bgcolor=#90ff90|950||bgcolor=#90ff90|983||bgcolor=#90ff90|1052||bgcolor=#90ff90|1028||bgcolor=#90ff90|990||bgcolor=#90ff90|1054||bgcolor=#90ff90|1073||bgcolor=#90ff90|1109||bgcolor=#90ff90|1134||bgcolor=#90ff90|1173||bgcolor=#90ff90|1236
|-
![http://meta.wikimedia.org/wiki/User:Sj Samuel Klein]
|bgcolor=#ff9090|836||bgcolor=#ff9090|910|| ||bgcolor=#90ff90|911||bgcolor=#90ff90|924||bgcolor=#90ff90|983||bgcolor=#90ff90|980||bgcolor=#90ff90|971||bgcolor=#90ff90|941||bgcolor=#90ff90|967||bgcolor=#90ff90|1019||bgcolor=#90ff90|1069||bgcolor=#90ff90|1099||bgcolor=#90ff90|1126||bgcolor=#90ff90|1183
|-
![http://meta.wikimedia.org/wiki/User:Harel Harel Cain]
|bgcolor=#ff9090|731||bgcolor=#ff9090|836||bgcolor=#ff9090|799|| ||bgcolor=#90ff90|896||bgcolor=#90ff90|892||bgcolor=#90ff90|964||bgcolor=#90ff90|904||bgcolor=#90ff90|917||bgcolor=#90ff90|959||bgcolor=#90ff90|1007||bgcolor=#90ff90|1047||bgcolor=#90ff90|1075||bgcolor=#90ff90|1080||bgcolor=#90ff90|1160
|-
![http://meta.wikimedia.org/wiki/User:Dedalus Ad Huikeshoven]
|bgcolor=#ff9090|674||bgcolor=#ff9090|781||bgcolor=#ff9090|764||bgcolor=#ff9090|806|| ||bgcolor=#90ff90|832||bgcolor=#90ff90|901||bgcolor=#90ff90|868||bgcolor=#90ff90|848||bgcolor=#90ff90|920||bgcolor=#90ff90|934||bgcolor=#90ff90|987||bgcolor=#90ff90|1022||bgcolor=#90ff90|1030||bgcolor=#90ff90|1115
|-
![http://meta.wikimedia.org/wiki/User:Cimon_Avaro Jussi-Ville Heiskanen]
|bgcolor=#ff9090|621||bgcolor=#ff9090|720||bgcolor=#ff9090|712||bgcolor=#ff9090|755||bgcolor=#ff9090|714|| ||bgcolor=#90ff90|841||bgcolor=#90ff90|798||bgcolor=#ff9090|737||bgcolor=#90ff90|827||bgcolor=#90ff90|850||bgcolor=#90ff90|912||bgcolor=#90ff90|970||bgcolor=#90ff90|943||bgcolor=#90ff90|1057
|-
![http://meta.wikimedia.org/wiki/User:Ryan_Postlethwaite Ryan Postlethwaite]
|bgcolor=#ff9090|674||bgcolor=#ff9090|702||bgcolor=#ff9090|726||bgcolor=#ff9090|756||bgcolor=#ff9090|772||bgcolor=#ff9090|770|| ||bgcolor=#90ff90|755||bgcolor=#90ff90|797||bgcolor=#90ff90|741||bgcolor=#90ff90|804||bgcolor=#90ff90|837||bgcolor=#90ff90|880||bgcolor=#90ff90|921||bgcolor=#90ff90|1027
|-
![http://meta.wikimedia.org/wiki/User:Sarcasticidealist Steve Smith]
|bgcolor=#ff9090|650||bgcolor=#ff9090|694||bgcolor=#ff9090|654||bgcolor=#ff9090|712||bgcolor=#ff9090|729||bgcolor=#ff9090|750||bgcolor=#ff9090|744|| ||bgcolor=#90ff90|778||bgcolor=#90ff90|734||bgcolor=#90ff90|796||bgcolor=#90ff90|840||bgcolor=#90ff90|876||bgcolor=#90ff90|884||bgcolor=#90ff90|1007
|-
![http://meta.wikimedia.org/wiki/User:Eclecticology Ray Saintonge]
|bgcolor=#ff9090|629||bgcolor=#ff9090|703||bgcolor=#ff9090|641||bgcolor=#ff9090|727||bgcolor=#ff9090|714||bgcolor=#90ff90|745||bgcolor=#ff9090|769||bgcolor=#ff9090|738|| ||bgcolor=#90ff90|789||bgcolor=#90ff90|812||bgcolor=#90ff90|848||bgcolor=#90ff90|879||bgcolor=#90ff90|899||bgcolor=#90ff90|987
|-
![http://meta.wikimedia.org/wiki/User:Swatjester Dan Rosenthal]
|bgcolor=#ff9090|595||bgcolor=#ff9090|654||bgcolor=#ff9090|609||bgcolor=#ff9090|660||bgcolor=#ff9090|691||bgcolor=#ff9090|724||bgcolor=#ff9090|707||bgcolor=#ff9090|699||bgcolor=#ff9090|711|| ||bgcolor=#90ff90|721||bgcolor=#90ff90|780||bgcolor=#90ff90|844||bgcolor=#90ff90|858||bgcolor=#90ff90|960
|-
![http://meta.wikimedia.org/wiki/User:Cspurrier Craig Spurrier]
|bgcolor=#ff9090|473||bgcolor=#ff9090|537||bgcolor=#ff9090|498||bgcolor=#ff9090|530||bgcolor=#ff9090|571||bgcolor=#ff9090|583||bgcolor=#ff9090|587||bgcolor=#ff9090|577||bgcolor=#ff9090|578||bgcolor=#ff9090|600|| ||bgcolor=#90ff90|646||bgcolor=#90ff90|721||bgcolor=#90ff90|695||bgcolor=#90ff90|845
|-
![http://meta.wikimedia.org/wiki/User:MBisanz Matthew Bisanz]
|bgcolor=#ff9090|472||bgcolor=#ff9090|498||bgcolor=#ff9090|465||bgcolor=#ff9090|509||bgcolor=#ff9090|508||bgcolor=#ff9090|534||bgcolor=#ff9090|473||bgcolor=#ff9090|507||bgcolor=#ff9090|531||bgcolor=#ff9090|513||bgcolor=#ff9090|552|| ||bgcolor=#90ff90|653||bgcolor=#90ff90|677||bgcolor=#90ff90|785
|-
![http://meta.wikimedia.org/wiki/User:Kmweber Kurt M. Weber]
|bgcolor=#ff9090|505||bgcolor=#ff9090|535||bgcolor=#ff9090|528||bgcolor=#ff9090|547||bgcolor=#ff9090|588||bgcolor=#ff9090|581||bgcolor=#ff9090|553||bgcolor=#ff9090|573||bgcolor=#ff9090|588||bgcolor=#ff9090|566||bgcolor=#ff9090|595||bgcolor=#ff9090|634|| ||bgcolor=#90ff90|679||bgcolor=#90ff90|787
|-
![http://meta.wikimedia.org/wiki/User:Skenmy Paul Williams]
|bgcolor=#ff9090|380||bgcolor=#ff9090|420||bgcolor=#ff9090|410||bgcolor=#ff9090|435||bgcolor=#ff9090|439||bgcolor=#ff9090|464||bgcolor=#ff9090|426||bgcolor=#ff9090|466||bgcolor=#ff9090|470||bgcolor=#ff9090|471||bgcolor=#ff9090|429||bgcolor=#ff9090|521||bgcolor=#ff9090|566|| ||bgcolor=#90ff90|754
|-
![http://meta.wikimedia.org/wiki/User:Thekohser Gregory Kohs]
|bgcolor=#ff9090|411||bgcolor=#ff9090|412||bgcolor=#ff9090|434||bgcolor=#ff9090|471||bgcolor=#ff9090|461||bgcolor=#ff9090|471||bgcolor=#ff9090|468||bgcolor=#ff9090|461||bgcolor=#ff9090|467||bgcolor=#ff9090|472||bgcolor=#ff9090|491||bgcolor=#ff9090|523||bgcolor=#ff9090|513||bgcolor=#ff9090|541||
|-
|+elections to Wikimedia's Board of Trustees in 2008:
|}

Each figure represents the number of voters who ranked the candidate at the left better than the candidate at the top. A figure in green represents a victory in that pairwise comparison by the candidate at the left. A figure in red represents a defeat in that pairwise comparison by the candidate at the left.


== External Resources ==
== External Resources ==
Line 649: Line 875:
=== General ===
=== General ===


* [http://m-schulze.webhop.net/propstat.pdf Proposed Statutory Rules for the Schulze Single-Winner Election Method] by Markus Schulze
* [http://m-schulze.9mail.de/propstat.pdf Proposed Statutory Rules for the Schulze Single-Winner Election Method] by Markus Schulze
* [http://www.citizensassembly.bc.ca/resources/submissions/csharman-10_0409201706-143.pdf A New Monotonic and Clone-Independent Single-Winner Election Method] by Markus Schulze (mirrors: [http://lists.gnu.org/archive/html/demexp-dev/2003-09/pdflQW7IlpAfC.pdf] [http://www.votingmatters.org.uk/ISSUE17/I17P3.PDF])
* [http://www.citizensassembly.bc.ca/resources/submissions/csharman-10_0409201706-143.pdf A New Monotonic and Clone-Independent Single-Winner Election Method] by Markus Schulze (mirrors: [http://lists.gnu.org/archive/html/demexp-dev/2003-09/pdflQW7IlpAfC.pdf] [http://www.votingmatters.org.uk/ISSUE17/I17P3.PDF])
* [http://m-schulze.webhop.net/schulze1.pdf A New Monotonic, Clone-Independent, Reversal Symmetric, and Condorcet-Consistent Single-Winner Election Method] by Markus Schulze
* [http://m-schulze.9mail.de/schulze1.pdf A New Monotonic, Clone-Independent, Reversal Symmetric, and Condorcet-Consistent Single-Winner Election Method] by Markus Schulze
* [http://m-schulze.webhop.net/schulze2.pdf Free Riding and Vote Management under Proportional Representation by the Single Transferable Vote] by Markus Schulze
* [http://m-schulze.9mail.de/schulze2.pdf Free Riding and Vote Management under Proportional Representation by the Single Transferable Vote] by Markus Schulze
* [http://m-schulze.webhop.net/schulze3.zip Implementing the Schulze STV Method] by Markus Schulze
* [http://m-schulze.9mail.de/schulze3.zip Implementing the Schulze STV Method] by Markus Schulze
* [http://m-schulze.webhop.net/schulze4.pdf A New MMP Method] by Markus Schulze
* [http://m-schulze.9mail.de/schulze4.pdf A New MMP Method] by Markus Schulze
* [http://m-schulze.webhop.net/schulze5.pdf A New MMP Method (Part 2)] by Markus Schulze
* [http://m-schulze.9mail.de/schulze5.pdf A New MMP Method (Part 2)] by Markus Schulze


=== Tutorials ===
=== Tutorials ===


* [http://www.informatik.uni-freiburg.de/~ki/teaching/ss09/gametheory/spieltheorie.pdf Spieltheorie] by Bernhard Nebel
* [http://m-schulze.webhop.net/serie3_9-10.pdf Schulze-Methode] by the University of Stuttgart
* [http://m-schulze.9mail.de/serie3_9-10.pdf Schulze-Methode] by the University of Stuttgart


=== Advocacy ===
=== Discussions ===
:''<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. -->
<!-- this section contains a lot of links; please try to keep it organized by the author's last name. -->
* [http://www.condorcet.org/emr/methods.shtml Election Methods Resource] by Blake Cretney
* [http://fc.antioch.edu/~james_green-armytage/vm/survey.htm#beatpath Voting Methods Survey] by James Green-Armytage
* [http://fc.antioch.edu/~james_green-armytage/vm/survey.htm#beatpath Voting Methods Survey] by James Green-Armytage
* [http://cec.wustl.edu/~rhl1/rbvote/desc.html Descriptions of ranked-ballot voting methods] by Rob LeGrand
* [https://www.cs.angelo.edu/~rlegrand/rbvote/desc.html Descriptions of ranked-ballot voting methods] by Rob LeGrand
* [http://accuratedemocracy.com/voting_rules.htm Accurate Democracy] by Rob Loring
* [http://accuratedemocracy.com/voting_rules.htm Accurate Democracy] by Rob Loring
* [http://rangevoting.org/SchulzeExplan.html Schulze beatpaths method] by Warren D. Smith
* [http://rangevoting.org/SchulzeExplan.html Schulze beatpaths method] by Warren D. Smith
Line 672: Line 905:
* [http://seehuhn.de/comp/vote.html The Debian Voting System] by Jochen Voss
* [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]
* [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 ===
=== Research papers ===


<!-- this section contains a lot of links; please try to keep it organized by the author's last name. -->
<!-- this section contains a lot of links; please try to keep it organized by the author's last name. -->
* [http://arxiv.org/PS_cache/arxiv/pdf/0810/0810.2263v1.pdf A Continuous Rating Method for Preferential Voting] by Rosa Camps, Xavier Mora, and Laia Saumell
* [http://m-schulze.webhop.net/pr304.pdf Social Choice Under Incomplete, Cyclic Preferences] by Jobst Heitzig
* [http://pj.freefaculty.org/Ukraine/PJ3_VotingSystemsEssay.pdf Voting Systems] by Paul E. Johnson
* [http://pj.freefaculty.org/Ukraine/PJ3_VotingSystemsEssay.pdf Voting Systems] by Paul E. Johnson
* [http://msdn.microsoft.com/en-us/magazine/dd148646.aspx Test Run: Group Determination in Software Testing] by James D. McCaffrey
* [http://congress.utu.fi/epcs2006/docs/A2_meskanen.pdf Distance from Consensus: a Theme and Variations] by Tommi Meskanen and Hannu Nurmi
* [http://congress.utu.fi/epcs2006/docs/A2_meskanen.pdf Distance from Consensus: a Theme and Variations] by Tommi Meskanen and Hannu Nurmi
* [http://www.soc.utu.fi/laitokset/iasm/research/iasm_wp2.PDF Analyzing Political Disagreement] by Tommi Meskanen and Hannu Nurmi
* [http://www.math.temple.edu/~wds/homepage/votedesc.pdf Descriptions of voting systems] by Warren D. Smith
* [http://m-schulze.webhop.net/votedesc.pdf Descriptions of voting systems] by Warren D. Smith
* [http://home.earthlink.net/~peter.a.taylor/swuusi.pdf Election Systems] by Peter A. Taylor
* [http://m-schulze-2.webhop.net/swuusi.pdf Election Systems] by Peter A. Taylor
* [http://m-schulze.9mail.de/wilke.pdf Personalisierung der Verhältniswahl durch Varianten der Single Transferable Vote] by Martin Wilke
* [http://dukespace.lib.duke.edu/dspace/bitstream/10161/1278/1/Wright_Barry.pdf Objective Measures of Preferential Ballot Voting Systems] by Barry Wright
* [http://m-schulze-2.webhop.net/wilke.pdf Personalisierung der Verhältniswahl durch Varianten der Single Transferable Vote] by Martin Wilke
* [http://www.cs.qub.ac.uk/~W.Liu/ecsqaru-paper-46.pdf Approaches to Constructing a Stratified Merged Knowledge Base] by Anbu Yue, Weiru Liu, and Anthony Hunter
* [http://www.cs.qub.ac.uk/~W.Liu/ecsqaru-paper-46.pdf Approaches to Constructing a Stratified Merged Knowledge Base] by Anbu Yue, Weiru Liu, and Anthony Hunter


Line 688: Line 923:


<!-- this section contains a lot of links; please try to keep it organized by the author's last name. -->
<!-- this section contains a lot of links; please try to keep it organized by the author's last name. -->
* Christoph Börgers (2009), ''[http://books.google.com/books?id=dccBaphP1G4C&pg=PA37#v=onepage&q=&f=false Mathematics of Social Choice: Voting, Compensation, and Division]'', SIAM, ISBN 0-8987-1695-0
* ''Understanding Modern Mathematics'' by Saul Stahl and Paul E. Johnson (ISBN 0-7637-3401-2)
* Saul Stahl and Paul E. Johnson (2006), ''[http://books.google.com/books?id=CMLL9sVGLb8C&pg=PA119#v=onepage&q=&f=false Understanding Modern Mathematics]'', Sudbury: Jones and Bartlett Publishers, ISBN 0-7637-3401-2
* ''Collective Decisions and Voting: The Potential for Public Choice'' [http://www.ashgate.com/pdf/SamplePages/Collective_Decisions_and_Voting_Index.pdf] by Nicolaus Tideman (ISBN 0-7546-4717-X)
* Nicolaus Tideman (2006), ''[http://books.google.com/books?id=RN5q_LuByUoC&pg=PA228#v=onepage&q=&f=false Collective Decisions and Voting: The Potential for Public Choice]'' [http://www.ashgate.com/pdf/SamplePages/Collective_Decisions_and_Voting_Index.pdf], Burlington: Ashgate, ISBN 0-7546-4717-X

=== Newspaper articles ===

* [http://www.heise.de/tp/r4/artikel/31/31832/1.html Entscheidungsfindung via Software] by Peter Mühlbauer (January 2010)


=== Software ===
=== Software ===
Line 697: Line 937:
* [http://condorcet-dd.sourceforge.net/ Condorcet with Dual Dropping Perl Scripts] by Mathew Goldstein
* [http://condorcet-dd.sourceforge.net/ Condorcet with Dual Dropping Perl Scripts] by Mathew Goldstein
* [http://condorcet.ericgorr.net/ Condorcet Voting Calculator] by Eric Gorr
* [http://condorcet.ericgorr.net/ Condorcet Voting Calculator] by Eric Gorr
* [http://selectricity.org/ Selectricity] and [http://rubyvote.rubyforge.org/ RubyVote] by Benjamin Mako Hill
* [http://selectricity.org/ Selectricity] and [http://rubyvote.rubyforge.org/ RubyVote] by Benjamin Mako Hill [http://web.mit.edu/newsoffice/2008/voting-tt0312.html] [http://labcast.media.mit.edu/?p=56]
* [http://relet.net/frog/?p=52 Java implementation of the Schulze method] by Thomas Hirsch
* [http://relet.net/frog/archives/52 Java implementation of the Schulze method] by Thomas Hirsch
* [https://bitbucket.org/capitol/schulze schulze implementation] implementation in c++ with python bindings by Alexander Kjäll
* [http://wiki.electorama.com/wiki/Electowidget Electowidget] by Rob Lanphier
* [http://wiki.electorama.com/wiki/Electowidget Electowidget] by Rob Lanphier
* [http://www.votator.com Votator.com] by Louis Philippe Lessard [http://www.votator.com/howitworks/]
* [http://www.livejournal.com/community/evan_tech/124253.html Haskell Condorcet Module] by Evan Martin
* [http://www.livejournal.com/community/evan_tech/124253.html Haskell Condorcet Module] by Evan Martin
* [http://www.cs.cornell.edu/andru/civs.html Condorcet Internet Voting Service (CIVS)] by Andrew Myers
* [http://www.cs.cornell.edu/andru/civs.html Condorcet Internet Voting Service (CIVS)] by Andrew Myers
* [http://betterpolls.com/ BetterPolls.com] by Brian Olson
* [http://betterpolls.com/ BetterPolls.com] by Brian Olson
* [http://www.openstv.org/ OpenSTV] by Jeffrey O'Neill
* [http://github.com/bradbeattie/Election-Web-Service Election Web Service] implements both the Schulze method and Schulze STV, with an associated interface at
[http://www.modernballots.com Modern Ballots]


=== Legislative project ===
=== Legislative project ===


* [http://groups.yahoo.com/group/Condorcet Condorcet Policy "Think Tank"] moderated by [http://jeffryfisher.net/Statesman Jeffry R. Fisher]
* [http://groups.yahoo.com/group/Condorcet Condorcet Policy "Think Tank"] moderated by [http://jeffryfisher.net/Statesman Jeffry R. Fisher]
* [http://www.azvotereform.com/ Arizonans for Competitive Elections Reform] [http://ballotpedia.org/wiki/index.php?title=Arizona_Competitive_Elections_Reform_Act_%282008%29] [http://azvotereform.zxq.net/booklet.pdf] [http://www.azcentral.com/members/Blog/PoliticalInsider/22368] [http://www.eastvalleytribune.com/story/111955] [http://www.ballot-access.org/2008/04/29/arizona-high-school-student-files-paperwork-for-initiatives-for-irv-and-easier-ballot-access/]
* [http://www.azsos.gov/election/2008/general/ballotmeasuretext/I-21-2008.pdf Arizonans for Condorcet Ranked Voting] [http://ballotpedia.org/wiki/index.php?title=Arizona_Competitive_Elections_Reform_Act_%282008%29] [http://www.azcentral.com/members/Blog/PoliticalInsider/22368] [http://www.ballot-access.org/2008/04/29/arizona-high-school-student-files-paperwork-for-initiatives-for-irv-and-easier-ballot-access/]


{{fromwikipedia}}
{{fromwikipedia}}


[[Category:Condorcet method]]
[[Category:Single-winner voting methods]]
[[Category:Smith-efficient Condorcet methods]]
[[Category:Defeat-dropping Condorcet methods]]
[[Category:Monotonic_electoral_systems]]
[[Category:Ranked voting methods]]
[[Category:Clone-independent electoral systems]]

Latest revision as of 14:36, 14 July 2023

Wikipedia has an article on:

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 compared in turn with 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 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.

The path heuristic

Each ballot contains a complete list of all candidates. Each voter ranks these candidates in order of preference. The individual voter may give the same preference to more than one candidate and he may keep candidates unranked. When a given voter does not rank all candidates, then it is presumed that this voter strictly prefers all ranked candidates to all not ranked candidates and that this voter is indifferent between all not ranked candidates.

Procedure

Suppose d[V,W] is the number of voters who strictly prefer candidate V to candidate W.

A path from candidate X to candidate Y of strength p is a sequence of candidates C(1),...,C(n) with the following five properties:

  1. C(1) is identical to X.
  2. C(n) is identical to Y.
  3. For all i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
  4. For all i = 1,...,(n-1): d[C(i),C(i+1)] ≥ p.

p[A,B], the strength of the strongest path from candidate A to candidate B, is the maximum value such that there is a path from candidate A to candidate B of that strength. If there is no path from candidate A to candidate B at all, then p[A,B] : = 0.

Candidate D is better than candidate E if and only if p[D,E] > p[E,D].

Candidate D is a potential winner if and only if p[D,E] ≥ p[E,D] for every other candidate E.

Remark

It is possible to prove that p[X,Y] > p[Y,X] and p[Y,Z] > p[Z,Y] together imply p[X,Z] > p[Z,X]. Therefore, it is guaranteed (1) that the above definition of "better" really defines a transitive relation and (2) that there is always at least one candidate D with p[D,E] ≥ p[E,D] for every other candidate E.

Implementation

Suppose C is the number of candidates. Then the strengths of the strongest paths can be calculated with the Floyd–Warshall algorithm.

Input: d[i,j] is the number of voters who strictly prefer candidate i to candidate j.

Output: Candidate i is a potential winner if and only if "winner[i] = true". 

 1 for i : = 1 to C
 2 begin
 3    for j : = 1 to C
 4    begin
 5       if ( i ≠ j ) then
 6       begin
 7          if ( d[i,j] > d[j,i] ) then
 8          begin
 9             p[i,j] : = d[i,j]
10          end
11          else
12          begin
13             p[i,j] : = 0
14          end
15       end
16    end
17 end
18
19 for i : = 1 to C
20 begin
21    for j : = 1 to C
22    begin
23       if ( i ≠ j ) then
24       begin
25          for k : = 1 to C
26          begin
27             if ( i ≠ k ) then
28             begin   
29                if ( j ≠ k ) then
30                begin
31                   p[j,k] : = max { p[j,k]; min { p[j,i]; p[i,k] } }
32                end
33             end
34          end
35       end
36    end
37 end
38
39 for i : = 1 to C
40 begin
41    winner[i] : = true
42 end
43
44 for i : = 1 to C
45 begin
46    for j : = 1 to C
47    begin
48       if ( i ≠ j ) then
49       begin
50          if ( p[j,i] > p[i,j] ) then
51          begin
52             winner[i] : = false
53          end
54       end
55    end
56 end

Examples

Example 1

Example (45 voters; 5 candidates):

5 ACBED
5 ADECB
8 BEDAC
3 CABED
7 CAEBD
2 CBADE
7 DCEBA
8 EBADC
d[*,A] d[*,B] d[*,C] d[*,D] d[*,E]
d[A,*] 20 26 30 22
d[B,*] 25 16 33 18
d[C,*] 19 29 17 24
d[D,*] 15 12 28 14
d[E,*] 23 27 21 31
The matrix of pairwise defeats looks as follows:

The critical defeats of the strongest paths are underlined.

... to A ... to B ... to C ... to D ... to E
from A ... A-(30)-D-(28)-C-(29)-B A-(30)-D-(28)-C A-(30)-D A-(30)-D-(28)-C-(24)-E
from B ... B-(25)-A B-(33)-D-(28)-C B-(33)-D B-(33)-D-(28)-C-(24)-E
from C ... C-(29)-B-(25)-A C-(29)-B C-(29)-B-(33)-D C-(24)-E
from D ... D-(28)-C-(29)-B-(25)-A D-(28)-C-(29)-B D-(28)-C D-(28)-C-(24)-E
from E ... E-(31)-D-(28)-C-(29)-B-(25)-A E-(31)-D-(28)-C-(29)-B E-(31)-D-(28)-C E-(31)-D
The strongest paths are:
p[*,A] p[*,B] p[*,C] p[*,D] p[*,E]
p[A,*] 28 28 30 24
p[B,*] 25 28 33 24
p[C,*] 25 29 29 24
p[D,*] 25 28 28 24
p[E,*] 25 28 28 31
The strengths of the strongest paths are:

Candidate E is a potential winner, because p[E,X] ≥ p[X,E] for every other candidate X.

As 25 = p[E,A] > p[A,E] = 24, candidate E is better than candidate A.

As 28 = p[E,B] > p[B,E] = 24, candidate E is better than candidate B.

As 28 = p[E,C] > p[C,E] = 24, candidate E is better than candidate C.

As 31 = p[E,D] > p[D,E] = 24, candidate E is better than candidate D.

As 28 = p[A,B] > p[B,A] = 25, candidate A is better than candidate B.

As 28 = p[A,C] > p[C,A] = 25, candidate A is better than candidate C.

As 30 = p[A,D] > p[D,A] = 25, candidate A is better than candidate D.

As 29 = p[C,B] > p[B,C] = 28, candidate C is better than candidate B.

As 29 = p[C,D] > p[D,C] = 28, candidate C is better than candidate D.

As 33 = p[B,D] > p[D,B] = 28, candidate B is better than candidate D.

Therefore, the Schulze ranking is E > A > C > B > D.

Example 2

Example (30 voters; 4 candidates):

5 ACBD
2 ACDB
3 ADCB
4 BACD
3 CBDA
3 CDBA
1 DACB
5 DBAC
4 DCBA
d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*] 11 20 14
d[B,*] 19 9 12
d[C,*] 10 21 17
d[D,*] 16 18 13
The matrix of pairwise defeats looks as follows:

The critical defeats of the strongest paths are underlined.

... to A ... to B ... to C ... to D
from A ... A-(20)-C-(21)-B A-(20)-C A-(20)-C-(17)-D
from B ... B-(19)-A B-(19)-A-(20)-C B-(19)-A-(20)-C-(17)-D
from C ... C-(21)-B-(19)-A C-(21)-B C-(17)-D
from D ... D-(18)-B-(19)-A D-(18)-B D-(18)-B-(19)-A-(20)-C
The strongest paths are:
p[*,A] p[*,B] p[*,C] p[*,D]
p[A,*] 20 20 17
p[B,*] 19 19 17
p[C,*] 19 21 17
p[D,*] 18 18 18
The strengths of the strongest paths are:

Candidate D is a potential winner, because p[D,X] ≥ p[X,D] for every other candidate X.

As 18 = p[D,A] > p[A,D] = 17, candidate D is better than candidate A.

As 18 = p[D,B] > p[B,D] = 17, candidate D is better than candidate B.

As 18 = p[D,C] > p[C,D] = 17, candidate D is better than candidate C.

As 20 = p[A,B] > p[B,A] = 19, candidate A is better than candidate B.

As 20 = p[A,C] > p[C,A] = 19, candidate A is better than candidate C.

As 21 = p[C,B] > p[B,C] = 19, candidate C is better than candidate B.

Therefore, the Schulze ranking is D > A > C > B.

Example 3

Example (30 voters; 5 candidates):

3 ABDEC
5 ADEBC
1 ADECB
2 BADEC
2 BDECA
4 CABDE
6 CBADE
2 DBECA
5 DECAB
d[*,A] d[*,B] d[*,C] d[*,D] d[*,E]
d[A,*] 18 11 21 21
d[B,*] 12 14 17 19
d[C,*] 19 16 10 10
d[D,*] 9 13 20 30
d[E,*] 9 11 20 0
The matrix of pairwise defeats looks as follows:

The critical defeats of the strongest paths are underlined.

... to A ... to B ... to C ... to D ... to E
from A ... A-(18)-B A-(21)-D-(20)-C A-(21)-D A-(21)-E
from B ... B-(19)-E-(20)-C-(19)-A B-(19)-E-(20)-C B-(19)-E-(20)-C-(19)-A-(21)-D B-(19)-E
from C ... C-(19)-A C-(19)-A-(18)-B C-(19)-A-(21)-D C-(19)-A-(21)-E
from D ... D-(20)-C-(19)-A D-(20)-C-(19)-A-(18)-B D-(20)-C D-(30)-E
from E ... E-(20)-C-(19)-A E-(20)-C-(19)-A-(18)-B E-(20)-C E-(20)-C-(19)-A-(21)-D
The strongest paths are:
p[*,A] p[*,B] p[*,C] p[*,D] p[*,E]
p[A,*] 18 20 21 21
p[B,*] 19 19 19 19
p[C,*] 19 18 19 19
p[D,*] 19 18 20 30
p[E,*] 19 18 20 19
The strengths of the strongest paths are:

Candidate B is a potential winner, because p[B,X] ≥ p[X,B] for every other candidate X.

As 19 = p[B,A] > p[A,B] = 18, candidate B is better than candidate A.

As 19 = p[B,C] > p[C,B] = 18, candidate B is better than candidate C.

As 19 = p[B,D] > p[D,B] = 18, candidate B is better than candidate D.

As 19 = p[B,E] > p[E,B] = 18, candidate B is better than candidate E.

As 20 = p[A,C] > p[C,A] = 19, candidate A is better than candidate C.

As 21 = p[A,D] > p[D,A] = 19, candidate A is better than candidate D.

As 21 = p[A,E] > p[E,A] = 19, candidate A is better than candidate E.

As 20 = p[D,C] > p[C,D] = 19, candidate D is better than candidate C.

As 30 = p[D,E] > p[E,D] = 19, candidate D is better than candidate E.

As 20 = p[E,C] > p[C,E] = 19, candidate E is better than candidate C.

Therefore, the Schulze ranking is B > A > D > E > C.

Example 4

Example (9 voters; 4 candidates):

3 ABCD
2 DABC
2 DBCA
2 CBDA
d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*] 5 5 3
d[B,*] 4 7 5
d[C,*] 4 2 5
d[D,*] 6 4 4
The matrix of pairwise defeats looks as follows:

The critical defeats of the strongest paths are underlined.

... to A ... to B ... to C ... to D
from A ... A-(5)-B A-(5)-C A-(5)-C-(5)-D
from B ... B-(5)-D-(6)-A B-(7)-C B-(5)-D
from C ... C-(5)-D-(6)-A C-(5)-D-(6)-A-(5)-B C-(5)-D
from D ... D-(6)-A D-(6)-A-(5)-B D-(6)-A-(5)-C
The strongest paths are:
p[*,A] p[*,B] p[*,C] p[*,D]
p[A,*] 5 5 5
p[B,*] 5 7 5
p[C,*] 5 5 5
p[D,*] 6 5 5
The strengths of the strongest paths are:

Candidate B and candidate D are potential winners, because p[B,X] ≥ p[X,B] for every other candidate X and p[D,Y] ≥ p[Y,D] for every other candidate Y.

As 7 = p[B,C] > p[C,B] = 5, candidate B is better than candidate C.

As 6 = p[D,A] > p[A,D] = 5, candidate D is better than candidate A.

Possible Schulze rankings are B > C > D > A, B > D > A > C, B > D > C > A, D > A > B > C, D > B > A > C, and D > B > C > A.

The Schwartz set heuristic

The Schwartz Set

The definition of a Schwartz set, as used in the Schulze method, is as follows:

  1. An unbeaten set is a set of candidates of whom none is beaten by anyone outside that set.
  2. An innermost unbeaten set is an unbeaten set that doesn't contain a smaller unbeaten set.
  3. The Schwartz set is the set of candidates who are in innermost unbeaten sets.

Procedure

The voters cast their ballots by ranking the candidates according to their preferences, just like for any other Condorcet election.

The Schulze method uses Condorcet pairwise matchups between the candidates and a winner is chosen in each of the matchups.

From there, the Schulze method operates as follows to select a winner (or create a ranked list):

  1. Calculate the Schwartz set based only on undropped defeats.
  2. 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.
  3. 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

The Situation

Imagine an election for the capital of Tennessee, a state in the United States that is over 500 miles east-to-west, and only 110 miles north-to-south. Let's say the candidates for the capital are Memphis (on the far west end), Nashville (in the center), Chattanooga (129 miles southeast of Nashville), and Knoxville (on the far east side, 114 northeast of Chattanooga). Here's the population breakdown by metro area (surrounding county):

  • Memphis (Shelby County): 826,330
  • Nashville (Davidson County): 510,784
  • Chattanooga (Hamilton County): 285,536
  • Knoxville (Knox County): 335,749

Let's say that in the vote, the voters vote based on geographic proximity. Assuming that the population distribution of the rest of Tennessee follows from those population centers, one could easily envision an election where the percentages of votes would be as follows:

42% of voters (close to Memphis)
1. Memphis
2. Nashville
3. Chattanooga
4. Knoxville

26% of voters (close to Nashville)
1. Nashville
2. Chattanooga
3. Knoxville
4. Memphis

15% of voters (close to Chattanooga)
1. Chattanooga
2. Knoxville
3. Nashville
4. Memphis

17% of voters (close to Knoxville)
1. Knoxville
2. Chattanooga
3. Nashville
4. Memphis

The results would be tabulated as follows:

Pairwise Election Results
A
Memphis Nashville Chattanooga Knoxville
BMemphis[A] 58%
[B] 42%
[A] 58%
[B] 42%
[A] 58%
[B] 42%
Nashville[A] 42%
[B] 58%
[A] 32%
[B] 68%
[A] 32%
[B] 68%
Chattanooga[A] 42%
[B] 58%
[A] 68%
[B] 32%
[A] 17%
[B] 83%
Knoxville[A] 42%
[B] 58%
[A] 68%
[B] 32%
[A] 83%
[B] 17%
Pairwise election results (won-lost-tied): 0-3-0 3-0-0 2-1-0 1-2-0
Votes against in worst pairwise defeat: 58%N/A68%83%
  • [A] indicates voters who preferred the candidate listed in the column caption to the candidate listed in the row caption
  • [B] indicates voters who preferred the candidate listed in the row caption to the candidate listed in the column caption
  • [NP] indicates voters who expressed no preference between either candidate

Pairwise Winners

First, list every pair, and determine the winner:

Pair Winner
Memphis (42%) vs. Nashville (58%) Nashville 58%
Memphis (42%) vs. Chattanooga (58%) Chattanooga 58%
Memphis (42%) vs. Knoxville (58%) Knoxville 58%
Nashville (68%) vs. Chattanooga (32%) Nashville 68%
Nashville (68%) vs. Knoxville (32%) Nashville 68%
Chattanooga (83%) vs. Knoxville (17%) Chattanooga: 83%

Note that absolute counts of votes can be used, or percentages of the total number of votes; it makes no difference.

Dropping

Next we start with our list of cities and their matchup wins/defeats

  • Nashville 3-0
  • Chattanooga 2-1
  • Knoxville 1-2
  • Memphis 0-3

Technically, the Schwartz set is simply Nashville as it beat all others 3 to 0.

Therefore, Nashville is the winner.

Ambiguity Resolution Example

Let's say there was an ambiguity. For a simple situation involving candidates A, B, and C.

  • A > B 72%
  • B > C 68%
  • C > A 52%

In this situation the Schwartz set is A, B, and C as they all beat someone.

The Schulze method then says to drop the weakest defeat, so we drop C > A and are left with

  • A > B 72% (as C has been removed from the Schwartz set and thus eliminated, since they no longer beat or tie anyone in the set)

Therefore, A is the winner.


(It may be more accessible to phrase that as "drop the weakest win", though purists may complain.)

Summary

In the (first) example election, the winner is Nashville. This would be true for any Condorcet method. 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 criteria

The Schulze method satisfies the following criteria:

  1. Mutual majority criterion
  2. Monotonicity criterion
  3. Pareto criterion
  4. Condorcet criterion
  5. Smith criterion (a.k.a. Generalized Condorcet criterion)
  6. local independence from irrelevant alternatives
  7. Schwartz criterion
  8. Plurality criterion
  9. the winner is always chosen from the Immune set
  10. the winner is always chosen from the CDTT set
  11. Minimal Defense criterion
  12. Strategy-Free criterion
  13. Generalized Strategy-Free criterion
  14. Strong Defensive Strategy criterion
  15. Weak Defensive Strategy criterion
  16. Summability criterion
  17. Independence of clones
  18. Blank Ballot Criterion
  19. Independence of Smith-dominated Alternatives

The Schulze method violates the following criteria:

  1. Participation criterion
  2. Consistency criterion
  3. invulnerability to compromising
  4. invulnerability to burying
  5. Favorite Betrayal criterion
  6. Later-no-harm criterion

History of the Schulze method

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 [1] [2] [3] [4] [5]. 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

Using the Floyd-Warshall algorithm, determining the winner (or the order of finish of all candidates) takes time, where 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).[1]

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.

Smith set-based variant

An example of the Smith set-based variation of the Schulze method.

A possible variation of Schulze (caution: not proposed, endorsed, or seriously analyzed by Markus Schulze) which is only Smith-efficient and not Schwartz-efficient (see the image to the right for an example) can be described as "Iteratively repeat the following two steps until there are no more pairwise defeats, at which point all of the remaining candidates are tied to win: 1) Eliminate all candidates not in the Smith set, and then 2) turn the weakest pairwise defeat into a pairwise victory for both candidates in the matchup." This can be argued to be simpler than regular Schulze, since the Smith set is easier to understand than the Schwartz set. It will return the same result as regular Schulze when there are no pairwise ties between any members of the Smith set. This variation could be called the cloneproof Smith sequential dropping method (though when dropping defeats, they are "flipped" to victories for both candidates in the matchup, rather than turned into a pairwise tie). It may be possible when using this variation to pretend a particular pairwise matchup simply didn't happen, rather than to say that both candidates in the matchup got a pairwise victory, when dropping defeats.

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:

JH RP SS RS
Jussi-Ville Heiskanen 841 798 737
Ryan Postlethwaite 770 755 797
Steve Smith 750 744 778
Ray Saintonge 745 769 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:

JH RP SS RS
Jussi-Ville Heiskanen 841 798 737
Ryan Postlethwaite 770 755 797
Steve Smith 750 744 778
Ray Saintonge 745 769 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:

RP SS RS
Ryan Postlethwaite 755 797
Steve Smith 744 778
Ray Saintonge 769 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

The Schulze method is not currently used in government elections. However, it is starting to receive support in some public organizations. Organizations which currently use the Schulze method are:

Wikimedia Foundation, 2008

It has been suggested that this article be merged into Category:Schulze method elections. (Discuss) Proposed since August 2019.

In June 2008, the Wikimedia Foundation used the Schulze method for the election to its Board of Trustees: One vacant seat had to be filled. There were 15 candidates, about 26,000 eligible voters, and 3,019 valid ballots.

As Chen was a clear Condorcet winner, he won the vacant seat. However, there was a tie for sixth to ninth position between Heiskanen, Postlethwaite, Smith, and Saintonge. Heiskanen beat Postlethwaite; Postlethwaite beat Smith; Smith beat Saintonge; Saintonge beat Heiskanen.

TC AB SK HC AH JH RP SS RS DR CS MB KW PW GK
Ting Chen 1086 1044 1108 1135 1151 1245 1190 1182 1248 1263 1306 1344 1354 1421
Alex Bakharev 844 932 984 950 983 1052 1028 990 1054 1073 1109 1134 1173 1236
Samuel Klein 836 910 911 924 983 980 971 941 967 1019 1069 1099 1126 1183
Harel Cain 731 836 799 896 892 964 904 917 959 1007 1047 1075 1080 1160
Ad Huikeshoven 674 781 764 806 832 901 868 848 920 934 987 1022 1030 1115
Jussi-Ville Heiskanen 621 720 712 755 714 841 798 737 827 850 912 970 943 1057
Ryan Postlethwaite 674 702 726 756 772 770 755 797 741 804 837 880 921 1027
Steve Smith 650 694 654 712 729 750 744 778 734 796 840 876 884 1007
Ray Saintonge 629 703 641 727 714 745 769 738 789 812 848 879 899 987
Dan Rosenthal 595 654 609 660 691 724 707 699 711 721 780 844 858 960
Craig Spurrier 473 537 498 530 571 583 587 577 578 600 646 721 695 845
Matthew Bisanz 472 498 465 509 508 534 473 507 531 513 552 653 677 785
Kurt M. Weber 505 535 528 547 588 581 553 573 588 566 595 634 679 787
Paul Williams 380 420 410 435 439 464 426 466 470 471 429 521 566 754
Gregory Kohs 411 412 434 471 461 471 468 461 467 472 491 523 513 541
elections to Wikimedia's Board of Trustees in 2008:

Each figure represents the number of voters who ranked the candidate at the left better than the candidate at the top. A figure in green represents a victory in that pairwise comparison by the candidate at the left. A figure in red represents a defeat in that pairwise comparison by the candidate at the left.

External Resources

General

Tutorials

Discussions

formerly "Advocacy"

This section contains various public discussions about the Schulze method.

2020

2019 and earlier

Research papers

Books

Newspaper articles

Software

Modern Ballots

Legislative project

This page uses Creative Commons Licensed content from Wikipedia (view authors).
  1. ↑ Csar, Theresa; Lackner, Martin; Pichler, Reinhard (2018-07). "Computing the Schulze Method for Large-Scale Preference Data Sets". Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Stockholm, Sweden: International Joint Conferences on Artificial Intelligence Organization: 180–187. doi:10.24963/ijcai.2018/25. ISBN 978-0-9992411-2-7. Check date values in: |date= (help)
Retrieved from "https://electowiki.org/wiki/Schulze_method?oldid=17461"