About Opentopia
Opentopia Directory Encyclopedia Tools

Schulze method

Encyclopedia : S : SC : SCH : Schulze method

The Schulze method is a voting system developed in 1997 by Markus Schulze that selects a single winner using votes that express preferences. The method can also be used to create a sorted list of winners. The Schulze method is also known as Schwartz Sequential Dropping (SSD), Cloneproof Schwartz Sequential Dropping (CSSD), Beatpath Method, Beatpath Winner, Path Voting, and Path Winner.

If there is a candidate who is preferred pairwise over the other candidates, when compared in turn with each of the others, the Schulze method guarantees that that candidate will win. Because of this property, the Schulze method is (by definition) a Condorcet method.

Many different heuristics for the Schulze method have been proposed. The most important heuristics are the path heuristic and the Schwartz heuristic.

Wikimedia Commons has media related to:
[

Example 1

Example (45 voters; 5 candidates):

5 ACBED
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 critical defeats of the strongest paths are underlined.

... to A ... to B ... to C ... to D ... 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 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 potential winner, because p[E,X] ≥ p[X,E] for every other candidate X.

Example 2

Example (30 voters; 4 candidates):

5 ACBD
2 ACDB
3 ADCB
4 BACD
3 CBDA
3 CDBA
1 DACB
5 DBAC
4 DCBA
d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*] 11 20 14
d[B,*] 19 9 12
d[C,*] 10 21 17
d[D,*] 16 18 13
The matrix of pairwise defeats looks as follows:

The critical defeats of the strongest paths are underlined.

... to A ... to B ... to C ... to D
from A ... A-(20)-C-(21)-B A-(20)-C A-(20)-C-(17)-D
from B ... B-(19)-A B-(19)-A-(20)-C B-(19)-A-(20)-C-(17)-D
from C ... C-(21)-B-(19)-A C-(21)-B C-(17)-D
from D ... D-(18)-B-(19)-A D-(18)-B D-(18)-B-(19)-A-(20)-C
The strongest paths are:

p[*,A] p[*,B] p[*,C] p[*,D]
p[A,*] 20 20 17
p[B,*] 19 19 17
p[C,*] 19 21 17
p[D,*] 18 18 18
The strengths of the strongest paths are:

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

Example 3

Example (30 voters; 5 candidates):

3 ABDEC
5 ADEBC
1 ADECB
2 BADEC
2 BDECA
4 CABDE
6 CBADE
2 DBECA
5 DECAB
d[*,A] d[*,B] d[*,C] d[*,D] d[*,E]
d[A,*] 18 11 21 21
d[B,*] 12 14 17 19
d[C,*] 19 16 10 10
d[D,*] 9 13 20 30
d[E,*] 9 11 20 0
The matrix of pairwise defeats looks as follows:

The critical defeats of the strongest paths are underlined.

... to A ... to B ... to C ... to D ... to E
from A ... A-(18)-B A-(21)-D-(20)-C A-(21)-D A-(21)-E
from B ... B-(19)-E-(20)-C-(19)-A B-(19)-E-(20)-C B-(19)-E-(20)-C-(19)-A-(21)-D B-(19)-E
from C ... C-(19)-A C-(19)-A-(18)-B C-(19)-A-(21)-D C-(19)-A-(21)-E
from D ... D-(20)-C-(19)-A D-(20)-C-(19)-A-(18)-B D-(20)-C D-(30)-E
from E ... E-(20)-C-(19)-A E-(20)-C-(19)-A-(18)-B E-(20)-C E-(20)-C-(19)-A-(21)-D
The strongest paths are:

p[*,A] p[*,B] p[*,C] p[*,D] p[*,E]
p[A,*] 18 20 21 21
p[B,*] 19 19 19 19
p[C,*] 19 18 19 19
p[D,*] 19 18 20 30
p[E,*] 19 18 20 19
The strengths of the strongest paths are:

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

Example 4

Example (9 voters; 4 candidates):

3 ABCD
2 DABC
2 DBCA
2 CBDA
d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*] 5 5 3
d[B,*] 4 7 5
d[C,*] 4 2 5
d[D,*] 6 4 4
The matrix of pairwise defeats looks as follows:

The critical defeats of the strongest paths are underlined.

Candidate B and candidate D are potential winners, because p[B,X] ≥ p[X,B] for every other candidate X and p[D,Y] ≥ p[Y,D] for every other candidate Y.

The Schwartz heuristic

The Schwartz set

The definition of a Schwartz set, as used in the Schulze method, is as follows:

  1. An unbeaten set is a set of candidates of whom none is beaten by anyone outside that set.
  2. An innermost unbeaten set is an unbeaten set that doesn't contain a smaller unbeaten set.
  3. The Schwartz set is the set of candidates who are in innermost unbeaten sets.

Procedure

The voters cast their ballots by ranking the candidates according to their preferences, just like for any other Condorcet election.

The Schulze method uses Condorcet pairwise matchups between the candidates and a winner is chosen in each of the matchups.

From there, the Schulze method operates as follows to select a winner (or create a ranked list):

  1. Calculate the Schwartz set based only on undropped defeats.
  2. If there are no defeats among the members of that set then they (plural in the case of a tie) win and the count ends.
  3. Otherwise, drop the weakest defeat among the candidates of that set. Go to 1.

An example

The situation

Imagine that the population of Tennessee, a state in the United States, is voting on the location of its capital. The population of Tennessee is concentrated around its four major cities, which are spread throughout the state. For this example, suppose that the entire electorate live in one of these four cities, and that they would like the capital to be established as close to their city as possible.

The candidates for the capital are:

  • Memphis, the state's largest city, with 42% of the voters, but located far from the other cities
  • Nashville, with 26% of the voters
  • Knoxville, with 17% of the voters
  • Chattanooga, with 15% of the voters
The preferences of the voters would be divided like this:

42% of voters
(close to Memphis) 		26% of voters
(close to Nashville) 		15% of voters
(close to Chattanooga) 		17% of voters
(close to Knoxville)
  1. Memphis
  2. Nashville
  3. Chattanooga
  4. Knoxville
  1. Nashville
  2. Chattanooga
  3. Knoxville
  4. Memphis
  1. Chattanooga
  2. Knoxville
  3. Nashville
  4. Memphis
  1. Knoxville
  2. Chattanooga
  3. Nashville
  4. Memphis

The results would be tabulated as follows:

Pairwise Election Results
A
Memphis Nashville Chattanooga Knoxville
BMemphis[A] 58%
[B] 42%
[A] 58%
[B] 42%
[A] 58%
[B] 42%
Nashville[A] 42%
[B] 58%
[A] 32%
[B] 68%
[A] 32%
[B] 68%
Chattanooga[A] 42%
[B] 58%
[A] 68%
[B] 32%
[A] 17%
[B] 83%
Knoxville[A] 42%
[B] 58%
[A] 68%
[B] 32%
[A] 83%
[B] 17%
Pairwise election results (won-lost-tied):

0-3-0 3-0-0 2-1-0 1-2-0
Votes against in worst pairwise defeat: 58%N/A68%83%

  • [A] indicates voters who preferred the candidate listed in the column caption to the candidate listed in the row caption
  • [B] indicates voters who preferred the candidate listed in the row caption to the candidate listed in the column caption
  • [NP] indicates voters who expressed no preference between either candidate

Pairwise winners

First, list every pair, and determine the winner:

Note that absolute counts of votes can be used, or percentages of the total number of votes; it makes no difference.

Dropping

Next we start with our list of cities and their matchup wins/defeats

  • Nashville 3-0
  • Chattanooga 2-1
  • Knoxville 1-2
  • Memphis 0-3
Technically, the Schwartz set is simply Nashville as it beat all others 3 to 0.

Therefore, Nashville is the winner.

Ambiguity resolution example

Let's say there was an ambiguity. For a simple situation involving candidates A, B, and C.

  • A > B 68%
  • B > C 72%
  • C > A 52%
In this situation the Schwartz set is A, B, and C as they all beat someone.

Schulze then says to drop the weakest defeat, so we drop C > A and are left with

  • A > B 68% (as C has been removed)
Therefore, A is the winner.

(It may be more accessible to phrase that as "drop the weakest win", though purists may complain.)

Summary

In the (first) example election, the winner is Nashville. This would be true for any Condorcet method. Using the first-past-the-post system and some other systems, Memphis would have won the election by having the most people, even though Nashville won every simulated pairwise election outright. Nashville would also have been the winner in a Borda count. Using Instant-runoff voting in this example would result in Knoxville winning, even though more people preferred Nashville over Knoxville.

Satisfied and failed criteria

Satisfied criteria

The Schulze method satisfies the following criteria:

  1. Non-imposition (a.k.a. citizen sovereignty)
  2. Non-dictatorial
  3. Pareto criterion
  4. Monotonicity criterion (a.k.a. mono-raise)
  5. Majority criterion
  6. Condorcet criterion (a.k.a. Condorcet winner criterion)
  7. Condorcet loser criterion
  8. Smith criterion (a.k.a. Generalized Condorcet criterion)
  9. Schwartz criterion
  10. Local independence from irrelevant alternatives (see below)
  11. Mutual majority criterion
  12. Independence of clones (See clones)
  13. Reversal symmetry
  14. [Mono-append]
  15. [Mono-add-plump]
  16. Resolvability criterion
If winning votes is used as the definition of defeat strength, it also satisfies:

  1. Woodall's plurality criterion
  2. [Woodall's CDTT criterion]
If margins as defeat strength is used, it also satisfies:

  1. [Symmetric-completion]

Failed criteria

The Schulze method violates the following criteria:

  1. All criteria that are incompatible with the Condorcet criterion (e.g. independence from irrelevant alternatives, participation, consistency, invulnerability to compromising, invulnerability to burying, [later-no-harm], [later-no-help])
  2. The Schulze method doesn't guarantee that the winner is always chosen from the [uncovered set].
  3. [Mono-remove-bottom]
  4. [Mono-add-top]

Independence of irrelevant alternatives

The Schulze method fails independence from irrelevant alternatives. However, the method adheres to a less strict property is sometimes called local independence from irrelevant alternatives. It says that if one candidate (X) wins an election, and a new alternative (Y) is added, X will win the election if Y is not in the Smith set. Local IIA implies the Condorcet criterion.

Use of the Schulze method

The Schulze method is not currently used in government elections. However, it is starting to receive support in some public organizations. Organizations which currently use the Schulze method are:

External resources

Note that these sources may refer to the Schulze method as CSSD, SSD, beatpath, path winner, etc.

General

Advocacy

Research papers

Software

 

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles
0123456789
ABCDEFGHIJ
KLMNOPQRST
UVWXYZ?

E-mail this article to:

Personal Message: