User:MarkusSchulze/Schulze method (draft)

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

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

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

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

Example (45 voters; 5 candidates):

5 ACBED (that is, 5 voters rank the candidates A = '1', C = '2', B = '3', E = '4', D = '5')
8 BEDAC
3 CABED
7 CAEBD
7 DCEBA
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:

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.

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.