User:MarkusSchulze/Short version of the Schulze method

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
This is a shortened and simplified version of this article.

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, Pirate Party of Sweden, Pirate Party of Germany, Debian, and Gentoo. It satisfies e.g. majority, majority loser, mutual majority, Condorcet, Condorcet loser, Smith, monotonicity, independence of clones, resolvability, and reversal symmetry.

Stage 1[edit]

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

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

Definitions:

A path from candidate X to candidate Y of strength z 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).
  4. d[C(i),C(i+1)] ≥ z for all i = 1,...,(n-1).
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 of this strength from candidate A to candidate B.
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 Schulze winner if and only if p[D,E] ≥ p[E,D] for every other candidate E.

Example[edit]

Example (21 voters; 4 candidates):

8 ACDB
2 BADC
4 CDBA
4 DBAC
3 DCBA
d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*] 8 14 10
d[B,*] 13 6 2
d[C,*] 7 15 12
d[D,*] 11 19 9
The matrix of pairwise defeats looks as follows:

The graph of pairwise defeats looks as follows:

Schulze method example7.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
from A ...
Schulze method example7 AB.svg
A-(14)-C-(15)-B
Schulze method example7 AC.svg
A-(14)-C
Schulze method example7 AD.svg
A-(14)-C-(12)-D
from B ...
Schulze method example7 BA.svg
B-(13)-A
Schulze method example7 BC.svg
B-(13)-A-(14)-C
Schulze method example7 BD.svg
B-(13)-A-(14)-C-(12)-D
from C ...
Schulze method example7 CA.svg
C-(15)-B-(13)-A
Schulze method example7 CB.svg
C-(15)-B
Schulze method example7 CD.svg
C-(12)-D
from D ...
Schulze method example7 DA.svg
D-(19)-B-(13)-A
Schulze method example7 DB.svg
D-(19)-B
Schulze method example7 DC.svg
D-(19)-B-(13)-A-(14)-C
The strongest paths are:
p[*,A] p[*,B] p[*,C] p[*,D]
p[A,*] 14 14 12
p[B,*] 13 13 12
p[C,*] 13 15 12
p[D,*] 13 19 13
The strengths of the strongest paths are:

Candidate D is a Schulze winner, because p[D,X] ≥ p[X,D] for every other candidate X.

As 14 = p[A,B] > p[B,A] = 13, candidate A is better than candidate B.

As 14 = p[A,C] > p[C,A] = 13, candidate A is better than candidate C.

As 15 = p[C,B] > p[B,C] = 13, candidate C is better than candidate B.

As 13 = p[D,A] > p[A,D] = 12, candidate D is better than candidate A.

As 19 = p[D,B] > p[B,D] = 12, candidate D is better than candidate B.

As 13 = p[D,C] > p[C,D] = 12, candidate D is better than candidate C.

Therefore, the Schulze ranking is D > A > C > B.

References[edit]