Difference between revisions of "Schulze method"
m |
m |
||
Line 555: | Line 555: | ||
# [http://www.spi-inc.org/ Software in the Public Interest (SPI)] [http://www.spi-inc.org/corporate/resolutions/resolution-2003-01-06.wta.1] | # [http://www.spi-inc.org/ Software in the Public Interest (SPI)] [http://www.spi-inc.org/corporate/resolutions/resolution-2003-01-06.wta.1] | ||
# [http://www.gentoo.org/ Gentoo Linux] [http://article.gmane.org/gmane.linux.gentoo.nfp/252/match=Condorcet] [http://article.gmane.org/gmane.linux.gentoo.nfp/256/match=CSSD] [http://article.gmane.org/gmane.linux.gentoo.weekly-news/121/match=Condorcet] [http://article.gmane.org/gmane.linux.gentoo.devel/28603/match=Condorcet+Cloneproof+Schwartz+Sequential+Dropping] | # [http://www.gentoo.org/ Gentoo Linux] [http://article.gmane.org/gmane.linux.gentoo.nfp/252/match=Condorcet] [http://article.gmane.org/gmane.linux.gentoo.nfp/256/match=CSSD] [http://article.gmane.org/gmane.linux.gentoo.weekly-news/121/match=Condorcet] [http://article.gmane.org/gmane.linux.gentoo.devel/28603/match=Condorcet+Cloneproof+Schwartz+Sequential+Dropping] | ||
− | # [http://www.userlinux.com/ UserLinux] [http://www.userlinux.com/cgi-bin/wiki.pl?Policy] [http://www5.cs.cornell.edu/cgi-bin/andru/icvs/results | + | # [http://www.userlinux.com/ UserLinux] [http://www.userlinux.com/cgi-bin/wiki.pl?Policy] [http://66.249.93.104/search?q=cache:GWhcrO6Ke8sJ:www5.cs.cornell.edu/cgi-bin/andru/icvs/results%3Fid%3DE_1bfeec1126d4a714+&hl=en] |
# [http://fr.wikipedia.org/wiki/Accueil WikipÃ©dia francophone] (The Schulze method is one of three methods recommended for decision-making.) [http://fr.wikipedia.org/wiki/WikipÃ©dia:Prise_de_dÃ©cision/Choix_dans_les_votes] | # [http://fr.wikipedia.org/wiki/Accueil WikipÃ©dia francophone] (The Schulze method is one of three methods recommended for decision-making.) [http://fr.wikipedia.org/wiki/WikipÃ©dia:Prise_de_dÃ©cision/Choix_dans_les_votes] | ||
# [http://www.lopsa.org/ League of Professional System Administrators (LOPSA)] (See article 8.3 of their [http://www.lopsa.org/bylaws bylaws]!) | # [http://www.lopsa.org/ League of Professional System Administrators (LOPSA)] (See article 8.3 of their [http://www.lopsa.org/bylaws bylaws]!) | ||
Line 568: | Line 568: | ||
# [http://jhac.acm.jhu.edu/bylaws.doc Johns Hopkins Animation Club (JHAC)] | # [http://jhac.acm.jhu.edu/bylaws.doc Johns Hopkins Animation Club (JHAC)] | ||
# [http://www.haifux.org/ Haifa Linux Club (Haifux)] [http://mirror.hamakor.org.il/archives/linux-il/01-2004/8135.html] | # [http://www.haifux.org/ Haifa Linux Club (Haifux)] [http://mirror.hamakor.org.il/archives/linux-il/01-2004/8135.html] | ||
− | # [http://fsck.truman.edu/ Free Software Club of Kirksville (FSCK)] [http://www5.cs.cornell.edu/cgi-bin/andru/civs/results | + | # [http://fsck.truman.edu/ Free Software Club of Kirksville (FSCK)] [http://66.249.93.104/search?q=cache:7cJM6uDYtCsJ:www5.cs.cornell.edu/cgi-bin/andru/civs/results%3Fid%3DE_614716deda9a4073+&hl=en] |
# [http://ns.goobergunch.net/wiki/index.php/Main_Page NationStates Wiki (NSwiki)] [http://ns.goobergunch.net/wiki/index.php/NSwiki:Logo_candidates/Vote] | # [http://ns.goobergunch.net/wiki/index.php/Main_Page NationStates Wiki (NSwiki)] [http://ns.goobergunch.net/wiki/index.php/NSwiki:Logo_candidates/Vote] | ||
# [http://www.rsabey.pwp.blueyonder.co.uk/rpc/fscc/ Five-Second Crossword Competition (FSCC)] [http://www.rsabey.pwp.blueyonder.co.uk/rpc/home/elect.html] | # [http://www.rsabey.pwp.blueyonder.co.uk/rpc/fscc/ Five-Second Crossword Competition (FSCC)] [http://www.rsabey.pwp.blueyonder.co.uk/rpc/home/elect.html] |
Revision as of 14:19, 13 January 2006
The Schulze method is a voting system developed by Markus Schulze that selects a single winner using votes that express preferences. The Schulze 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 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. Note that this is different from some other preference voting systems such as Borda and Instant-runoff voting, which do not make this guarantee.
Many different heuristics for the Schulze method have been proposed. The most important heuristics are the path heuristic and the Schwartz heuristic.
Contents
The path heuristic
Each ballot contains a complete list of all candidates. Each voter ranks these candidates in order of preference. The individual voter may give the same preference to more than one candidate and he may keep candidates unranked. When a given voter does not rank all candidates, then it is presumed that this voter strictly prefers all ranked candidates to all not ranked candidates and that this voter is indifferent between all not ranked candidates.
Procedure
Suppose d[V,W] is the number of voters who strictly prefer candidate V to candidate W.
A path from candidate X to candidate Y of strength z is an ordered set of candidates C(1),...,C(n) with the following four properties:
- C(1) is identical to X.
- C(n) is identical to Y.
- For i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
- For i = 1,...,(n-1): d[C(i),C(i+1)] ≥ z.
If there is a p such that there is a path from candidate A to candidate B of strength p and no path from candidate B to candidate A of strength p, then candidate A disqualifies candidate B.
Candidate D is a potential winner if and only if there is no candidate E such that candidate E disqualifies candidate D.
Examples
A path from candidate X to candidate Y is an ordered set of candidates C(1),...,C(n) with the following three properties:
- C(1) is identical to X.
- C(n) is identical to Y.
- For i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
The strength of the path C(1),...,C(n) is min { d[C(i),C(i+1)] | i = 1,...,(n-1) }.
In other words: The strength of a path is the strength of its weakest link.
p[A,B] : = max { min { d[C(i),C(i+1)] | i = 1,...,(n-1) } | C(1),...,C(n) is a path 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.
Then the Schulze method can be described as follows: Candidate A is a potential winner if and only if p[A,B] ≥ p[B,A] for every other candidate B.
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 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 |
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 |
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 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 |
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 |
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 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 |
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 |
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 critical defeats of the strongest paths are underlined.
... to A | ... to B | ... to C | ... to D | |
---|---|---|---|---|
from A ... | A-(5)-B | A-(5)-C | A-(5)-C-(5)-D | |
from B ... | B-(5)-D-(6)-A | B-(7)-C | B-(5)-D | |
from C ... | C-(5)-D-(6)-A | C-(5)-D-(6)-A-(5)-B | C-(5)-D | |
from D ... | D-(6)-A | D-(6)-A-(5)-B | D-(6)-A-(5)-C |
p[*,A] | p[*,B] | p[*,C] | p[*,D] | |
---|---|---|---|---|
p[A,*] | 5 | 5 | 5 | |
p[B,*] | 5 | 7 | 5 | |
p[C,*] | 5 | 5 | 5 | |
p[D,*] | 6 | 5 | 5 |
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:
- An unbeaten set is a set of candidates of whom none is beaten by anyone outside that set.
- An innermost unbeaten set is an unbeaten set that doesn't contain a smaller unbeaten set.
- 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):
- Calculate the Schwartz set based only on undropped defeats.
- 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.
- Otherwise, drop the weakest defeat among the candidates of that set. Go to 1.
An Example
The Situation
Imagine an election for the capital of Tennessee, a state in the United States that is over 500 miles east-to-west, and only 110 miles north-to-south. Let's say the candidates for the capital are Memphis (on the far west end), Nashville (in the center), Chattanooga (129 miles southeast of Nashville), and Knoxville (on the far east side, 114 northeast of Chattanooga). Here's the population breakdown by metro area (surrounding county):
- Memphis (Shelby County): 826,330
- Nashville (Davidson County): 510,784
- Chattanooga (Hamilton County): 285,536
- Knoxville (Knox County): 335,749
Let's say that in the vote, the voters vote based on geographic proximity. Assuming that the population distribution of the rest of Tennessee follows from those population centers, one could easily envision an election where the percentages of votes would be as follows:
42% of voters (close to Memphis) |
26% of voters (close to Nashville) |
15% of voters (close to Chattanooga) |
17% of voters (close to Knoxville) |
The results would be tabulated as follows:
A | |||||
---|---|---|---|---|---|
Memphis | Nashville | Chattanooga | Knoxville | ||
B | Memphis | [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/A | 68% | 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:
Pair | Winner |
---|---|
Memphis (42%) vs. Nashville (58%) | Nashville 58% |
Memphis (42%) vs. Chattanooga (58%) | Chattanooga 58% |
Memphis (42%) vs. Knoxville (58%) | Knoxville 58% |
Nashville (68%) vs. Chattanooga (32%) | Nashville 68% |
Nashville (68%) vs. Knoxville (32%) | Nashville 68% |
Chattanooga (83%) vs. Knoxville (17%) | Chattanooga: 83% |
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 72%
- B > C 68%
- C > A 52%
In this situation the Schwartz set is A, B, and C as they all beat someone.
The Schulze method then says to drop the weakest defeat, so we drop C > A and are left with
- A > B 72% (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. Using Instant-runoff voting in this example would result in Knoxville winning, even though more people preferred Nashville over Knoxville.
History
The Schulze method has been proposed by Markus Schulze in 1997. See e.g. here, here, and here!
Satisfied Criteria
The Schulze method satisfies the following criteria:
- Mutual majority criterion
- Monotonicity criterion
- Pareto criterion
- Condorcet criterion
- Smith criterion (a.k.a. Generalized Condorcet criterion)
- local independence from irrelevant alternatives
- Schwartz criterion
- Plurality criterion
- the winner is always chosen from the Immune set
- the winner is always chosen from the CDTT set
- Minimal Defense criterion
- Strategy-Free criterion
- Generalized Strategy-Free criterion
- Strong Defensive Strategy criterion
- Weak Defensive Strategy criterion
- Summability criterion
- Independence of clones
- Neutrality of Spoiled Ballots
The Schulze method violates the following criteria:
- Participation criterion
- Consistency criterion
- invulnerability to compromising
- invulnerability to burying
- Favorite Betrayal criterion
- Later-no-harm 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:
- Debian [1] [2]
- Software in the Public Interest (SPI) [3]
- Gentoo Linux [4] [5] [6] [7]
- UserLinux [8] [9]
- WikipÃ©dia francophone (The Schulze method is one of three methods recommended for decision-making.) [10]
- League of Professional System Administrators (LOPSA) (See article 8.3 of their bylaws!)
- Sender Policy Framework (SPF) [11]
- Mathematical Knowledge Management Interest Group (MKM-IG) (The MKM-IG uses Condorcet with dual dropping. That means: The Schulze ranking and the ranked pairs ranking are calculated and the winner is the top-ranked candidate of that of these two rankings that has the better Kemeny score.) [12] [13] [14]
- Park Alumni Society (PAS) [15]
- Kingman Hall [16] [17]
- Blitzed [18]
- Leader of the Free World (LFW) / Open Elections / Simply Working Preferential Web Election (SWPWE) [19] [20]
- Democratic Experience (DemExp) (See section 30.6 of this paper!)
- Glasnost / Easter Eggs / libre-entreprise
- Johns Hopkins Animation Club (JHAC)
- Haifa Linux Club (Haifux) [21]
- Free Software Club of Kirksville (FSCK) [22]
- NationStates Wiki (NSwiki) [23]
- Five-Second Crossword Competition (FSCC) [24]
- CivicEvolution [25]
- Libertarian Party at Colorado State University (LPCSU) [26]
Furthermore, the fact that the Schulze method is a part of Debian's voting software ("Debian Vote Engine", Devotee) means that it is the standard voting system in all Debian user groups (DUGs).
External Resources
Papers:
- A New Monotonic and Clone-Independent Single-Winner Election Method by Markus Schulze (mirror1, mirror2, mirror3)
- Descriptions of ranked-ballot voting methods by Rob LeGrand
- Election Methods Resource by Blake Cretney
- Election Methods and Criteria by Kevin Venzke
- Election Systems by Peter A. Taylor
- Voting Systems by Paul E. Johnson
- The Maximize Affirmed Majorities voting procedure (MAM) by Steve Eppley
- The Debian Voting System by Jochen Voss
- A Survey of Basic Voting Methods by James Green-Armytage
- Single-Winner Methods by Mike Ossipoff
- Accurate Democracy by Rob Loring
- Social Choice Under Incomplete, Cyclic Preferences by Jobst Heitzig
- A mailing list containing technical discussions about election methods
- Proposed statutory rules for the Schulze method
Software:
- Condorcet Internet Voting Service (CIVS) by Andrew Myers
- Condorcet Voting Calculator by Eric Gorr
- BetterPolls.com by Brian Olson
- A different way to vote by Anguo Ma
- Voting Software Project by Blake Cretney
- Condorcet with Dual Dropping Perl Scripts by Mathew Goldstein
- Haskell Condorcet Module by Evan Martin
This page uses Creative Commons Licensed content from Wikipedia (view authors). |