Schulze method

The Schulze method (after Markus Schulze) is an electoral process from the family of preferential elections , with which a single winner is determined. It is currently the most popular method of holding elections in which the voter ranks candidates by rank.

The Schulze method is a Condorcet method , i. That is, that it selects a candidate who would defeat any other candidate in a pairwise comparison as the winner, if one exists.

Markus Schulze developed the method in 1997. The first publications date from 2003 and 2006. The Schulze method was first used in 2003 (by Software in the Public Interest ), 2003 (by Debian ) and 2005 (by Gentoo Linux ).

Explanation

Each voter receives a complete list of all candidates . He ranks the candidates by assigning numbers to them. A small number is better than a larger number, but only the order counts. Candidates with the same number are ranked in the same place. Candidates without a number are together in last place - as if the voter had assigned them the largest possible number.

Number of voters

The number of voters who prefer candidate A over candidate B (i.e., who have a smaller number on A than B) is expressed by d [A, B].

The value of d is counted from the votes cast

• d [B, A] is the number of voters who find candidate B better than A.
• d [A, B] is the number of voters who find candidate A better than B.

For these values ​​it is irrelevant whether there are other candidates and whether these are classified better or worse than A and B or between the two.

definition

The Schulze method is defined as follows:

A path ( path ) X by the candidate to the candidate Y is the strength of such a sequence of candidates C (1), ..., C (n) having the following characteristics:

1. ${\displaystyle C(1)=X}$, d. H. the path starts at X.
2. ${\displaystyle C(n)=Y}$, d. H. the path ends at Y.
3. ${\displaystyle \forall i\in \{1,\dots ,(n-1)\}:d[C(i),C(i+1)]>d[C(i+1),C(i)]}$, d. H. each candidate on the way wins the pairwise comparison against the candidate following him.
4. ${\displaystyle \forall i\in \{1,\dots ,(n-1)\}:d[C(i),C(i+1)]\geq z}$, d. H. each candidate en route is preferred to the candidate following him by at least z voters.
5. ${\displaystyle \exists i\in \{1,\dots ,(n-1)\}:d[C(i),C(i+1)]=z}$, d. H. at least one of these comparisons is supported by (only) exactly z voters.

If a path C (1),…, C (n) has the strength z, the arcs of this path for which d [C (i), C (i + 1)] = z applies, are called “critical victories” . They are the weakest wins along the way.

p [A, B], the strength of the strongest path from candidate A to candidate B, is the largest value so that there is a path of this strength from candidate A to candidate B. p [A, B]: = 0 if there is no path from candidate A to candidate B.

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.

It can be shown that the “ better ” relation is transitive . There is always at least one potential winner.

example 1

Example (45 voters; 5 candidates):

	Ranks
# Voters	1.	2.	3.	4th	5.
5	A> C> B> E> D
5	A> D> E> C> B
8th	B> E> D> A> C
3	C> A> B> E> D
7th	C> A> E> B> D
2	C> B> A> D> E
7th	D> C> E> B> A
8th	E> B> A> D> C

Pairwise matrix

Table that compares each candidate with each other. The fields marked in red are still used. For example, candidate B was preferred to candidate A by 25 votes.

	there]	d [*, B]	d [*, C]	d [*, D]	d [*, E]
there,*]		20th	26th	30th	22nd
d [B, *]	25th		16	33	18th
d [C, *]	19th	29		17th	24
d [D, *]	15th	12	28		14th
d [E, *]	23	27	21st	31

Pairwise graph

Weighted arrow graph from the table above. You can see the arrow from candidate B to candidate A with the weight from the table above, 25.

The strongest ways

Of the connections between candidates, the one in which the weakest link is strongest is sought. Figuratively speaking, the strongest chain is sought. How do you 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 the 28 are used further.

You can imagine the process from the point of view of a transport company that wants to transport as many parcels as possible from one city to the other at once (regardless of how long the journey is). Without intermediate storage, of course, only as much can be transported as the capacity of the smallest means of transport that is used on the way: If the parcels are transported first by ferry, then by truck and finally by train, then the truck is probably the smallest. Compared to another route (e.g. that includes a car), the truck is the weakest link in the strongest chain .

Often this weakest link in the strongest chain is also called "critical victory". They are underlined here .

	... according to A	... according to B	... after C	... according to D	... according 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 strengths of the strongest ways

The weakest link of the strongest connection as found above is entered in a table. Then in pairs it is compared again who beats whom, marked red in the table below.

	p [*, A]	p [*, B]	p [*, C]	p [*, D]	p [*, E]
p [A, *]		28	28	30th	24
p [B, *]	25th		28	33	24
p [C, *]	25th	29		29	24
p [D, *]	25th	28	28		24
p [E, *]	25th	28	28	31

Result

The winner according to the Schulze method is candidate E, since p [E, X] ≥ p [X, E] for every other candidate X.

• Because 25 = p [E, A]> p [A, E] = 24, candidate E is better than candidate A.
• Because 28 = p [E, B]> p [B, E] = 24, candidate E is better than candidate B.
• Because 28 = p [E, C]> p [C, E] = 24, candidate E is better than candidate C.
• Because 31 = p [E, D]> p [D, E] = 24, candidate E is better than candidate D.
• Because 28 = p [A, B]> p [B, A] = 25, candidate A is better than candidate B.
• Because 28 = p [A, C]> p [C, A] = 25, candidate A is better than candidate C.
• Because 30 = p [A, D]> p [D, A] = 25, candidate A is better than candidate D.
• Because 29 = p [C, B]> p [B, C] = 28, candidate C is better than candidate B.
• Because 29 = p [C, D]> p [D, C] = 28, candidate C is better than candidate D.
• Because 33 = p [B, D]> p [D, B] = 28, candidate B is better than candidate D.

The Schulze ranking is therefore E> A> C> B> D.

Example 2

Example (9 voters; 4 candidates):

	Ranks
# Voters	1.	2.	3.	4th
3	A> B> C> D
2	D> A> B> C
2	D> B> C> A
2	C> B> D> A

Pairwise matrix

	there]	d [*, B]	d [*, C]	d [*, D]
there,*]		5	5	3
d [B, *]	4th		7th	5
d [C, *]	4th	2		5
d [D, *]	6th	4th	4th

Pairwise graph

The strongest ways

The critical victories of the strongest paths are underlined .

	... according to A	... according to B	... after C	... according to D
from A ...		A- (5) -B	A- (5) -C	A- (5) -B- (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 strengths of the strongest ways

	p [*, A]	p [*, B]	p [*, C]	p [*, D]
p [A, *]		5	5	5
p [B, *]	5		7th	5
p [C, *]	5	5		5
p [D, *]	6th	5	5

Result

Potential winners according to the Schulze method are therefore candidate B and candidate D, since (1) p [B, X] ≥ p [X, B] for every other candidate X and (2) p [D, Y] ≥ p For any other candidate, [Y, D] is Y.

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

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

Possible Schulze rankings are therefore 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

Be Cthe number of candidates. Then the strengths of the strongest paths can be calculated using the Floyd and Warshall algorithm.

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

Output: p[i,j]is the strength of the strongest path from candidate ito 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 are also known under the names Beatpath , Beatpaths , Beatpath Method , Beatpath Winner , Path Voting , Path Winner , Schwartz Sequential Dropping (SSD) and Cloneproof Schwartz Sequential Dropping (CSSD).

The Schulze method fulfills the following criteria (for an explanation of the most important criteria, see the section on quality criteria in the article on social choice theory ):

1. Majority criterion
2. Mutual majority criterion
3. Monotonicity criterion (also known as non-negative responsiveness, mono-raise)
4. Pareto criterion
5. Condorcet criterion
6. Condorcet loser criterion
7. Smith criterion (also referred to as Generalized Condorcet criterion)
8. Local independence from irrelevant alternatives
9. Schwartz criterion
10. Strategy-Free criterion
11. Generalized Strategy-Free criterion
12. Strong Defensive Strategy criterion
13. Weak Defensive Strategy criterion
14. Summability criterion
15. Independence of clones
16. non-dictatorial
17. universality
18. Woodall's plurality criterion
19. Woodall's CDTT criterion
20. Minimal defense criterion
21. Resolvability
22. Reversal symmetry
23. mono-append
24. mono-add-plump

The Schulze Method hurts

1. the consistency criterion ,
2. the participation criterion,
3. independence from irrelevant alternatives
4. as well as the favorite betrayal criterion.

Applications

Template for the electronic ballot papers for the elections to the Board of Trustees of the Wikimedia Foundation

The Schulze method is currently not used in state elections. However, it is being used more and more in private organizations. She is u. a. has been used in the following organizations:

• Wikimedia Foundation
• Pirate Party Germany
• Pirate Party Sweden
• Pirate Party of Austria
• Debian
• Ubuntu
• Software in the Public Interest
• Gentoo Foundation
• Sender Policy Framework
• Free Software Foundation Europe (FSFE)
• KDE
• Kingman Hall
• TopCoder
• GNU Privacy Guard
• Golden Geek Award
• Student council of the Albert Ludwig University of Freiburg
• Professional association of paediatricians

See also

• Ranked pairs
• Social choice theory
• Condorcet paradox
• LiquidFeedback

literature

• Christoph Börgers: Mathematics of Social Choice: Voting, Compensation, and Division . SIAM 2009, ISBN 0-89871-695-0 .
• Saul Stahl, Paul E. Johnson: Understanding Modern Mathematics . Jones & Bartlett Publishing, London a. a. 2007, ISBN 0-7637-3401-2 , pp. 119 ff.
• Nicolaus Tideman: Collective Decisions and Voting: The Potential for Public Choice . Ashgate Publishing, 2006, ISBN 0-7546-4717-X , p. 228 ff.

Web links

Commons : Schulze method  - album with pictures, videos and audio files

• Rosa Camps, Xavier Mora, Laia Saumell: A Continuous Rating Method for Preferential Voting . (PDF; 1.76 MB)
• Paul E. Johnson: Voting Systems . (PDF; 324 kB)
• Rob LeGrand: Descriptions of ranked-ballot voting methods .
• Rob Loring: Accurate Democracy .
• James D. McCaffrey: Test Run: Group Decisions in Software Tests . MSDN
• Tommi Meskanen, Hannu Nurmi: Distance from Consensus: a Theme and Variations . (PDF; 130 kB) In: Bruno Simeone, Friedrich Pukelsheim (Eds.): Mathematics and democracy : recent advances in voting systems and collective choice. Studies in choice and welfare. Springer, Berlin a. a. 2006, ISBN 3-540-35603-7 , pp. 117-132, here pp. 120 ff.
• Massimo Narizzano, Luca Pulina, Armando Tacchella: Ranking and Reputation Systems in the QBF Competition . (PDF; 455 kB) In: AI * IA '07 Proceedings of the 10th Congress of the Italian Association for Artificial Intelligence on AI * IA 2007: Artificial Intelligence and Human-Oriented Computing. Springer, Berlin / Heidelberg 2007, ISBN 978-3-540-74781-9 .
• Markus Schulze: Schulze Method FAQ
• Markus Schulze: A New Monotonic and Clone-Independent Single-Winner Election Method . (PDF; 74 kB) In: Voting Matters , 17, 2003, pp. 9-19.
• Kevin Venzke: Election Methods and Criteria .
• Jochen Voss: The Debian Voting System .
• Barry Wright: Objective Measures of Preferential Ballot Voting Systems . (PDF; 289 kB) Thesis Duke University, Durham NC 2009.

Individual evidence

1. ^ Condorcet sub-cycle rule , Election Methods Mailing List, October 3, 1997
2. ↑ Markus Schulze: A new monotonic and clone-independent single-winner election method . (PDF; 75 kB) In: Voting Matters , issue 17, 2003, pp. 9-19
3. ^ Nicolaus Tideman: Collective Decisions and Voting: The Potential for Public Choice . Ashgate Publishing, 2006. Saul Stahl, Paul E. Johnson: Understanding Modern Mathematics . Jones & Bartlett Publishing, 2006
4. ↑ Markus Schulze: A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method . (PDF; 577 kB) July 2007 (English)
5. ^ DR Woodall: Properties of Preferential Election Rules . December 1994
6. ^ Board election to use preference voting, May 2008
7. ↑ Press release of the Pirate Party Germany ( Memento of the original from May 29, 2011 in the Internet Archive ) Info: The archive link was inserted automatically and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. , August 2010 
8. ↑ Sample selection of the Swedish pirates , January 2010
9. ↑ wiki.piratenpartei.at
10. ^ Constitution for the Debian Project, Appendix A6
11. ↑ Ubuntu IRC Council Position , May 2012
12. ^ Process for adding new board members, January 2003
13. ^ Council Election Procedures ( Memento from July 16, 2011 in the Internet Archive )
14. ↑ § 6 Paragraph 3 of the Articles of Association (PDF; 112 kB)
15. ↑ Article 3.4.1 of the Rules of Procedures for Online Voting
16. ^ Kingman adopts Condorcet voting, April 2005
17. ↑ GnuPG Logo Vote, November 2006 ( Memento of the original from December 16, 2006 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. 
18. ↑ Golden Geek Awards
19. ↑ Rules of Procedure of the Student Council of the Albert Ludwig University of Freiburg. (PDF FDP, 53 kB) In: u-asta.uni-freiburg.de. May 13, 2014, accessed June 24, 2014 . 
20. ^ Statutes of the BVKJ