Schulze method

From Electowiki

Jump to: navigation, search

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.

Contents

[edit] 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.

[edit] 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.

[edit] 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.

[edit] 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

[edit] Examples

[edit] 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.

[edit] 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.

[edit] 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.

[edit] 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.

[edit] The Schwartz set heuristic

[edit] 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.

[edit] 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.

[edit] An Example

[edit] 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):

CondorcetTennesee.png
  • 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

[edit] Pairwise Winners

First, list every pair, and determine the winner:

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

[edit] 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.

[edit] 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)

Therefore, A is the winner.


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

[edit] 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.

[edit] 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. Neutrality of Spoiled Ballots

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

[edit] 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).

[edit] 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:

[edit] Wikimedia Foundation, 2008

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.

TCABSKHCAHJHRPSSRSDRCSMBKWPWGK
Ting Chen 10861044110811351151124511901182124812631306134413541421
Alex Bakharev 844 93298495098310521028990105410731109113411731236
Samuel Klein 836910 91192498398097194196710191069109911261183
Harel Cain 731836799 89689296490491795910071047107510801160
Ad Huikeshoven 674781764806 832901868848920934987102210301115
Jussi-Ville Heiskanen 621720712755714 8417987378278509129709431057
Ryan Postlethwaite 674702726756772770 7557977418048378809211027
Steve Smith 650694654712729750744 7787347968408768841007
Ray Saintonge 629703641727714745769738 789812848879899987
Dan Rosenthal 595654609660691724707699711 721780844858960
Craig Spurrier 473537498530571583587577578600 646721695845
Matthew Bisanz 472498465509508534473507531513552 653677785
Kurt M. Weber 505535528547588581553573588566595634 679787
Paul Williams 380420410435439464426466470471429521566 754
Gregory Kohs 411412434471461471468461467472491523513541
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.

[edit] External Resources

[edit] General

[edit] Tutorials

[edit] Advocacy

[edit] Research papers

[edit] Books

[edit] Newspaper articles

[edit] Software

Modern Ballots

[edit] Legislative project

This page uses Creative Commons Licensed content from Wikipedia (view authors).
Retrieved from "http://wiki.electorama.com/wiki/Schulze_method"
Personal tools