# Schulze method: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

# Encyclopedia

The Schulze method is a voting system developed in 1997 by Markus Schulze that selects a single winner using votes that express preferences. The 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 pairwise over the other candidates, when compared in turn with each of the others, the Schulze method guarantees that candidate will win. Because of this property, the Schulze method is (by definition) a Condorcet method.

Currently, the Schulze method is the most widespread Condorcet method (list). The Schulze method is used by several organizations including Wikimedia, Debian, Gentoo, and Software in the Public Interest.

Many different heuristics for computing the Schulze method have been proposed. The most important heuristics are the path heuristic and the Schwartz set heuristic that are described below. All heuristics find the same winner and only differ in the details of the computational procedure to determine this winner.

## The path heuristic

Under the Schulze method (as well as under other preferential single-winner election methods), each ballot contains a complete list of all candidates and the individual voter ranks this list in order of preference. Under a common ballot layout (as shown in the image to the right), ascending numbers are used, whereby the voter places a '1' beside the most preferred candidate, a '2' beside the second-most preferred, and so forth.

Each voter may ...

• ... give the same preference to more than one candidate. This indicates that this voter is indifferent between these candidates.
• ... skip preferences. However, skipping preferences has no impact on the result of the elections, since only the order, in which the candidates are ranked, matters and not the absolute numbers of the preferences.
• ... keep candidates unranked. When a voter doesn't rank all candidates, then this is interpreted as if this voter:
... (1) strictly prefers all ranked to all unranked candidates, and
... (2) is indifferent among all unranked candidates.

The basic idea of the path heuristic for the Schulze method is the concept of indirect defeats, the so-called paths.

If candidate C(1) pairwise beats candidate C(2), candidate C(2) pairwise beats candidate C(3), candidate C(3) pairwise beats candidate C(4), ..., and C(n-1) pairwise beats candidate C(n), then we say that there is a path from candidate C(1) to candidate C(n). The strength of the path C(1),...,C(n) is the weakest pairwise defeat in this sequence.

Example Schulze method ballot

In other words:

• Suppose d[V,W] is the number of voters who strictly prefer candidate V to candidate W.
• A path is a sequence of candidates C(1),...,C(n) with d[C(i),C(i+1)] > d[C(i+1),C(i)] for all i = 1,...,(n-1).
• The strength of the path C(1),...,C(n) is the minimum of all d[C(i),C(i+1)] for i = 1,...,(n-1).

The strength of the strongest path from candidate A to candidate B is the maximum of the strengths of all paths from candidate A to candidate B.

Candidate A pairwise beats candidate B indirectly if either

• the strength of the strongest path from candidate A to candidate B is stronger than the strength of the strongest path from candidate B to candidate A or
• there is a path from candidate A to candidate B and no path from candidate B to candidate A.

Indirect defeats are transitive. That means: If candidate A pairwise beats candidate B indirectly and candidate B pairwise beats candidate C indirectly, then also candidate A pairwise beats candidate C indirectly. Therefore, no tie-breaker is needed for indirect defeats.

### Procedure

Let d[V,W] be 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 properties:

1. C(1) = X and C(n) = Y.
2. For all i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
3. For all i = 1,...,(n-1): d[C(i),C(i+1)] ≥ p.
4. There exists an i, 1 ≤ i ≤ n-1 such that: 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].[1]:§2.3 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.

### Example

Example (45 voters; 5 candidates):

5 ACBED (that is, 5 voters have order of preference: A > C > B > E > D)
8 BEDAC
3 CABED
7 CAEBD
7 DCEBA
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 graph of pairwise defeats looks as follows:

The strength of a path is the strength of its weakest link. For each pair of candidates X and Y, the following table lists the strongest path from candidate X to candidate Y. 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 A ...
from B ...
B-(25)-A
B-(33)-D-(28)-C
B-(33)-D
B-(33)-D-(28)-C-(24)-E
from B ...
from C ...
C-(29)-B-(25)-A
C-(29)-B
C-(29)-B-(33)-D
C-(24)-E
from C ...
from D ...
D-(28)-C-(29)-B-(25)-A
D-(28)-C-(29)-B
D-(28)-C
D-(28)-C-(24)-E
from D ...
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
from E ...
... to A ... to B ... to C ... to D ... to E
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.

### Implementation

Suppose C is the number of candidates. Then the strengths of the strongest paths can be calculated with the Floyd–Warshall algorithm.[1]:§2.4 The following Pascal-like pseudocode illustrates the determination of such a path.

Input: d[i,j] is the number of voters who strictly prefer candidate i to candidate j.
Output: p[i,j] is the strength of the strongest path from candidate i to candidate j.
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
```

## The Schwartz set heuristic

### Procedure

The Schwartz set heuristic for the Schulze method is an iterative heuristic.

At each stage, we proceed as follows:

1. For each pair of undropped candidates X and Y: If there is a directed path of undropped links from candidate X to candidate Y, then we write "X → Y"; otherwise we write "not X → Y".
2. For each pair of undropped candidates V and W: If "V → W" and "not W → V", then candidate W is dropped and all links, that start or end in candidate W, are dropped.
3. The weakest undropped link is dropped. If several undropped links tie as weakest, all of them are dropped.

The procedure ends when all links have been dropped. The winners are the undropped candidates.

### Example

Example (30 voters; 4 candidates):

3 ACDB
9 BACD
8 CDAB
5 DABC
5 DBCA
d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*] 16 17 12
d[B,*] 14 19 9
d[C,*] 13 11 20
d[D,*] 18 21 10
The matrix of pairwise defeats looks as follows:

The graph of pairwise defeats looks as follows:

We get: "A → B", "A → C", "A → D", "B → A", "B → C", "B → D", "C → A", "C → B", "C → D", "D → A", "D → B", and "D → C".

As there is no pair of candidates V and W with "V → W" and "not W → V", no candidate can be dropped.

The weakest undropped link (A:B=16:14) is dropped.

Thus, we get:

We get: "A → B", "A → C", "A → D", "B → A", "B → C", "B → D", "C → A", "C → B", "C → D", "D → A", "D → B", and "D → C".

As there is no pair of candidates V and W with "V → W" and "not W → V", no candidate can be dropped.

The weakest undropped link (A:C=17:13) is dropped.

Thus, we get:

We get: "not A → B", "not A → C", "not A → D", "B → A", "B → C", "B → D", "C → A", "C → B", "C → D", "D → A", "D → B", and "D → C".

As "B → A" and "not A → B", candidate A is dropped and all links, that start or end in candidate A, are dropped.

Thus, we get:

The weakest undropped link (B:C=19:11) is dropped.

Thus, we get:

We get: "not B → C", "not B → D", "C → B", "C → D", "D → B", and "not D → C".

As "C → B" and "not B → C", candidate B is dropped and all links, that start or end in candidate B, are dropped; as "C → D" and "not D → C", candidate D is dropped and all links, that start or end in candidate D, are dropped.

As candidate C is the unique undropped candidate, candidate C is the unique winner.

## Satisfied and failed criteria

### Satisfied criteria

The Schulze method satisfies the following criteria:

If winning votes is used as the definition of defeat strength, it also satisfies:

If margins as defeat strength is used, it also satisfies:

### Failed criteria

The Schulze method violates all criteria that are incompatible with the Condorcet criterion, such as:

#### Independence of irrelevant alternatives

The Schulze method fails independence of irrelevant alternatives. However, the method adheres to a less strict property that is sometimes called independence of Smith-dominated alternatives. It says that if one candidate (X) wins an election, and a new alternative (Y) is added, X will win the election if Y is not in the Smith set. Local IIA implies the Condorcet criterion.

## Comparison with other preferential single-winner election methods

The following table compares the Schulze method with other preferential single-winner election methods:

Schulze Ranked Pairs Kemeny-Young MiniMax Nanson Baldwin Instant-runoff voting Coombs Contingent voting Sri Lankan contingent voting Supplementary voting Borda Bucklin Monotonic Condorcet Condorcet loser Majority Majority loser Mutual majority Smith ISDA Clone independence Reversal symmetry Polynomial time Participation, Consistency Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes No Yes No No Yes Yes No Yes No No No No No No Yes No No Yes Yes Yes Yes Yes Yes No No Yes Yes No No Yes Yes Yes Yes Yes Yes No No No Yes No No No Yes Yes Yes Yes No No Yes No Yes No No No Yes Yes Yes Yes No No No No Yes No No No Yes Yes Yes No No No No No Yes No No No No Yes No No No No No No Yes No No No No Yes No No No No No No Yes No Yes No Yes No Yes No No No No Yes Yes Yes Yes No No Yes Yes Yes No No No No Yes No Yes No No Yes No No No No No No Yes Yes Yes No No No Yes No No No No No Yes Yes

This is the main difference between the Schulze method and the Ranked Pairs method:

Suppose the MinMax score of a set X of candidates is the strength of the strongest pairwise win of a candidate A ∉ X against a candidate B ∈ X. Then the Schulze method, but not the Ranked Pairs method, guarantees that the winner is always a candidate of the set with minimum MinMax score.[1]:§9 So, in some sense, the Schulze method minimizes the strongest pairwise win that has to be overturned when determining the winner.

## History of the Schulze method

The Schulze method was developed by Markus Schulze in 1997. The first times that the Schulze method was discussed in a public mailing list were in 1998 [2] and in 2000 [3]. In the following years, the Schulze method has been adopted e.g. by Software in the Public Interest (2003) [4], Debian (2003) [5], Gentoo (2005), TopCoder (2005), and the French Wikipedia (2005). The first books on the Schulze method were written by Tideman (2006) and by Stahl and Johnson (2006). In the then following years, the Schulze method has been adopted e.g. by Wikimedia (2008), KDE (2008), and the Pirate Party of Sweden (2009).

## Use of the Schulze method

sample ballot for Wikimedia's Board of Trustees elections

The Schulze method is not currently used in parliamentary elections. However, it has been used for parliamentary primaries in the Swedish Pirate Party. It is also starting to receive support in other public organizations. Organizations which currently use the Schulze method are:

## Notes

1. ^ a b c d e f g h i j k
2. ^ See:
3. ^ See:
4. ^ a b Process for adding new board members, January 2003
5. ^ a b Constitutional Amendment: Condorcet/Clone Proof SSD Voting Method, June 2003
6. ^ Election of the Annodex Association committee for 2007, February 2007
7. ^ Condorcet method for admin voting, January 2005
8. ^ See:
9. ^ Project Logo, October 2009
10. ^ Codex Alpe Adria Competitions
11. ^ Fellowship Guidelines
12. ^ Report on HackSoc Elections, December 2008
13. ^ Adam Helman, Family Affair Voting Scheme - Schulze Method
14. ^ See:
15. ^ appendix 2 of the constitution
16. ^ Logo Competition, May 2009
17. ^ See:
18. ^ Guidance Document
19. ^ article XI section 2 of the bylaws
20. ^ See:
21. ^ See:
22. ^ See:
23. ^ GnuPG Logo Vote, November 2006
24. ^ §14 of the bylaws
25. ^ User Voting Instructions
26. ^ Haskell Logo Competition, March 2009
27. ^ A club by any other name ..., April 2009
28. ^ section 3.4.1 of the Rules of Procedures for Online Voting
29. ^ See:
30. ^ Knight Foundation awards \$5000 to best created-on-the-spot projects, June 2009
31. ^ See:
32. ^ article 8.3 of the bylaws
33. ^ See:
34. ^ Lumiera Logo Contest, January 2009
35. ^ article 5 of the constitution
36. ^ The MKM-IG uses Condorcet with dual dropping. That means: The Schulze ranking and the 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. See:
37. ^ Wahlmodus
38. ^ Benjamin Mako Hill, Voting Machinery for the Masses, July 2008
39. ^ Wahlen zum Neo-2-Freeze: Formalitäten, February 2010
40. ^ See:
41. ^ 2009 Director Elections
42. ^ NSC Jersey election, NSC Jersey vote, September 2007
43. ^ Thomas Goorden, CS community city ambassador elections on January 19th 2008 in Antwerp and ..., November 2007
44. ^ Voting Procedures
45. ^ See:
46. ^ 2006 Community for Pittsburgh Ultimate Board Election, September 2006
47. ^ LogoVoting, December 2007
48. ^ See:
49. ^ Squeak Oversight Board Election 2010, March 2010
50. ^ See:
51. ^ Election status update, September 2009
52. ^ See:
53. ^ See:
54. ^ See:
55. ^ See:
56. ^ The Schulze method is one of three methods recommended for decision-making. See here.
57. ^ See e.g. here (May 2009), here (August 2009), and here (December 2009).
58. ^ See here and here.
59. ^ See:
60. ^ See here.

# Simple English

Redirecting to Schulze method