Schulze method: Wikis

Advertisements
  
  

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

From Wikipedia, the free 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.

Contents

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.

Advertisements

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)
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 graph of pairwise defeats looks as follows:

Schulze method example1.svg

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 ...
Schulze method example1 AB.svg
A-(30)-D-(28)-C-(29)-B
Schulze method example1 AC.svg
A-(30)-D-(28)-C
Schulze method example1 AD.svg
A-(30)-D
Schulze method example1 AE.svg
A-(30)-D-(28)-C-(24)-E
from A ...
from B ...
Schulze method example1 BA.svg
B-(25)-A
Schulze method example1 BC.svg
B-(33)-D-(28)-C
Schulze method example1 BD.svg
B-(33)-D
Schulze method example1 BE.svg
B-(33)-D-(28)-C-(24)-E
from B ...
from C ...
Schulze method example1 CA.svg
C-(29)-B-(25)-A
Schulze method example1 CB.svg
C-(29)-B
Schulze method example1 CD.svg
C-(29)-B-(33)-D
Schulze method example1 CE.svg
C-(24)-E
from C ...
from D ...
Schulze method example1 DA.svg
D-(28)-C-(29)-B-(25)-A
Schulze method example1 DB.svg
D-(28)-C-(29)-B
Schulze method example1 DC.svg
D-(28)-C
Schulze method example1 DE.svg
D-(28)-C-(24)-E
from D ...
from E ...
Schulze method example1 EA.svg
E-(31)-D-(28)-C-(29)-B-(25)-A
Schulze method example1 EB.svg
E-(31)-D-(28)-C-(29)-B
Schulze method example1 EC.svg
E-(31)-D-(28)-C
Schulze method example1 ED.svg
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:

Schulze method example6a.svg

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:

Schulze method example6b.svg

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:

Schulze method example6c.svg

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:

Schulze method example6d.svg

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

Thus, we get:

Schulze method example6e.svg

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:

Monotonic Condorcet Condorcet loser Majority Majority loser Mutual majority Smith ISDA Clone independence Reversal symmetry Polynomial time Participation, Consistency
Schulze Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No
Ranked Pairs Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No
Kemeny-Young Yes Yes Yes Yes Yes Yes Yes Yes No Yes No No
MiniMax Yes Yes No Yes No No No No No No Yes No
Nanson No Yes Yes Yes Yes Yes Yes No No Yes Yes No
Baldwin No Yes Yes Yes Yes Yes Yes No No No Yes No
Instant-runoff voting No No Yes Yes Yes Yes No No Yes No Yes No
Coombs No No Yes Yes Yes Yes No No No No Yes No
Contingent voting No No Yes Yes Yes No No No No No Yes No
Sri Lankan contingent voting No No No Yes No No No No No No Yes No
Supplementary voting No No No Yes No No No No No No Yes No
Borda Yes No Yes No Yes No No No No Yes Yes Yes
Bucklin Yes No No Yes Yes Yes No No No No Yes No
Plurality Yes No No Yes No No No No No No Yes Yes
Anti-plurality 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 Schulze, Markus (August 21, 2009). "A New Monotonic, Clone-Independent, Reversal Symmetric, and Condorcet-Consistent Single-Winner Election Method". http://m-schulze.webhop.net/schulze1.pdf. 
  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.

External links

General

Tutorials

Advocacy

Research papers

Books

Software

Legislative projects


Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message