Schulze method
The Schulze method ( according to Mark Schulze ) is a selection method from the family of preferred options, with which a single winner is determined. It is currently the most common method to carry out elections in which voters rank candidates classified by.
The Schulze method is a Condorcet method, that is, that they, as the winner selects a candidate who would beat each other candidate in pairwise comparison, if one exists.
Markus Schulze has developed the method in 1997. The first publications date from 2003 and 2006., The Schulze method was used for the first time in 2003 (of Software in the Public Interest), 2003 (from Debian) and 2005 ( Gentoo Linux).
- 2.1 Example of an implementation in Pascal
Explanation
Each voter receives a complete list of all the candidates. He ranks the candidates by writing numbers to the candidates. A small number is better than a larger, but only counts the order. Candidates with the same number are ranked in the same place. Candidates without a number are together in last place - as if the voters would have respectively ascribed to them the greatest number.
Number of voters
The number of voters who prefer candidate A to candidate B (that is, have a smaller number than in B indicated in A), is expressed by d [A, B].
The value of d is counted from the voting
- D [ B, A ] is the number of how many voters find candidates B vs. A better.
- D [ A, B ] is the number of how many selector find candidates A to B better.
For these values , it is irrelevant whether there are other candidates, whether they are better or worse than between A and B classified.
Definition
The Schulze method is defined as follows:
It can be shown that the " better " relation is transitive. There is thus always at least a potential winner.
Example 1
Example ( 45 voters; 5 candidates):
Pairwise matrix
Table which compares each candidate with each other. The fields marked in red be used. For example, candidate B of 25 votes was against candidate A is preferred.
Pairwise graph
Graph with weighted arrows from the table from above. You can see the arrow of Candidate B to Candidate A with the weight from the above table, 25
The strongest paths
Of the connections between candidates that is sought, where the weakest link is strongest. Figuratively speaking, the strongest chain is searched. How to get from A to B?
- From A to C to B, the weakest link is from A to C with 26
- From A to D to C to B, the weakest link is D to C with 28 This chain is stronger and 28 continue to be used.
Often this weakest link of the strongest chain is also called " critical victory". You are underlined here.
The strengths of the most powerful ways
The weakest link of the strongest connection as found above, is entered into a table. Then again compared in pairs, who whom the bell, again highlighted in the table below in red.
Result
Winner after the Schulze method is a candidate E, since p [E, X ] ≥ p [ X, E ] is for every other candidate X.
- Because 25 = p [E, A] > p [ A, E ] = 24 is better than candidate A. Candidate E
- Because 28 = p [ E, B ]> p [ B, E ] = 24 is better than candidate B. Candidate E
- Because 28 = p [ E, C ]> p [ C, E ] = 24 is candidate e better than candidate C.
- Because 31 = p [ E, D ]> p [ D, E] = 24 is candidate e better than candidate D.
- Because 28 = p [A, B ]> p [ B, A ] = 25 is better than candidate B. Candidate A
- Because 28 = p [ A, C ]> p [ C, A ] = 25 is better than candidate A candidate C.
- Because 30 = p [ A, D ]> p [ D, A ] = 25 is better than candidate A candidate D.
- Because 29 = p [ C, B ]> p [ B, C ] = 28 is better than candidate B. Candidate C
- Because 29 = p [ C, D ]> p [ D, C ] = 28 is candidate C better than candidate D.
- Because 33 = p [ B, D ]> p [ D, B ] = 28 Candidate B is better than candidate D.
The Schulze ranking is thus E> A> C > B> D.
Example 2
Example ( 9 voters, 4 candidates):
Pairwise matrix
Pairwise graph
The strongest paths
The critical victories of the strongest paths are underlined.
The strengths of the most powerful ways
Result
Potential winner after the Schulze method are thus candidate B and candidate D, because (1) p [ B, X ] ≥ p [ X, B ] is for every other candidate X and ( 2) p [ D, Y ] ≥ p [ Y, D ] is for every other candidate Y.
Because 7 = p [ B, C ]> p [ C, B ] = 5 is better than Candidate B Candidate C.
Because 6 = p [ D, A ]> p [ A, D ] = 5 is a candidate D better than candidate A.
Possible Schulze rankings are thus 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.
Implementation
Let C be the number of candidates. Then the strengths of the strongest means using the algorithm of Floyd and Warshall can be calculated.
Input: d [i, j] is the number of voters that the candidate i j strictly prefer the candidate.
Output: p [i, j ] is the strength of the strongest path from candidate i to candidate j.
Example of an implementation in Pascal
For i: = 1 to C do begin for j: = 1 to C do begin if ( i < > j ) then begin if ( d [i, j ]> d [ j, i] ) then begin P [i, j]: = d [ i, j] end else begin P [i, j]: = 0 end end end end for i: = 1 to C do begin for j: = 1 to C do begin if ( i < > j ) then begin for k: = 1 to C do begin if ( i < > k ) then begin if ( j < > k ) then begin p [ j, k ]: = max ( p [ j, k ], min (P [j, i], P [i, k]) ) end end end end end end Heuristics and properties
Special heuristics of the Schulze method is also known under the name Beatpath, Beatpaths, Beatpath Method, Beatpath Winner, Path Voting, Path Winner, Schwartz Sequential Dropping (SSD ) and Schwartz Sequential Dropping Clone Proof (CSSD ).
The Schulze method satisfies the following criteria ( For an explanation of the most important criteria, see section quality criteria in the article social choice theory. ):
Violated the Schulze method
Applications
The Schulze method is not currently used in state elections. However, it takes more and more application in private organizations. It is, inter alia, been used in the following organizations: