User:MarkusSchulze/Schulze method (draft)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

The Schulze method is a voting system to fill a single seat. The method is also known as Schwartz Sequential Dropping (SSD), Cloneproof Schwartz Sequential Dropping (CSSD), Beatpath Method, Beatpath Winner, Path Voting, and Path Winner. It is used by several organizations including Wikimedia, Debian, Gentoo, and KDE.

Stage 1[change | change source]

sample ballot for Wikimedia's Board of Trustees elections

Each ballot contains a list of all candidates. Each voter ranks these candidates in order of preference. Each voter gives a '1' to his favorite candidate, a '2' to his second favorite candidate, a '3' to his third favorite candidate, etc..

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 between all unranked candidates.

Stage 2[change | change source]

For each pair of candidates V and W, we calculate the number of voters who strictly prefer candidate V to candidate W. This number will be denoted "d[V,W]".

Stage 3[change | change source]

Definitions:

A path from candidate X to candidate Y is a sequence of candidates C(1),...,C(n) with the following properties:
  1. C(1) is identical to X.
  2. C(n) is identical to Y.
  3. 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).
In other words: The strength of a path is the strength of its weakest link.
p[A,B] is the maximum of the strengths of all paths from candidate A to candidate B.
In other words: p[A,B] is the strength of the strongest path from candidate A to candidate B.
If there is no path from candidate A to candidate B at all, then p[A,B] : = 0.

For each pair of candidates D and E, we calculate p[D,E].

Candidate D is better than candidate E if and only if p[D,E] > p[E,D].

Candidate D is a Schulze winner if and only if p[D,E] ≥ p[E,D] for every other candidate E.

Example[change | change source]

Example (45 voters; 5 candidates):

5 ACBED (that is, 5 voters rank the candidates A = '1', C = '2', B = '3', E = '4', D = '5')
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 weakest links 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 Schulze 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.

References[change | change source]