User:MarkusSchulze/Short version of the Schulze method

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

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

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 of strength z is a sequence of candidates C(1),...,C(n) with the following properties:

C(1) is identical to X.
C(n) is identical to Y.
d[C(i),C(i+1)] > d[C(i+1),C(i)] for all i = 1,...,(n-1).
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

Example (21 voters; 4 candidates):

8 ACDB

2 BADC

4 CDBA

4 DBAC

3 DCBA

The matrix of pairwise defeats looks as follows:
	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 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.

The strongest paths are:
	... to A	... to B	... to C	... to D
from A ...		A-(14)-C-(15)-B	A-(14)-C	A-(14)-C-(12)-D
from B ...	B-(13)-A		B-(13)-A-(14)-C	B-(13)-A-(14)-C-(12)-D
from C ...	C-(15)-B-(13)-A	C-(15)-B		C-(12)-D
from D ...	D-(19)-B-(13)-A	D-(19)-B	D-(19)-B-(13)-A-(14)-C