Anonymous user
Schulze method: Difference between revisions
mayor cleanup
imported>MarkusSchulze (major cleanup) |
imported>MarkusSchulze (mayor cleanup) |
||
Line 13:
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''
:# C(1) is identical to X.
:# C(n) is identical to Y.
:# For all i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
:# For all i = 1,...,(n-1): d[C(i),C(i+1)] ≥
Candidate D is
=== Examples ===▼
=== Implementation ===
Suppose ''C'' is the number of candidates. Then the strengths of the strongest paths can be calculated with the Floyd–Warshall algorithm.
▲:# For i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
Output: Candidate i is a potential winner if and only if "winner[i] = true".
1 '''for''' i : = 1 '''to''' ''C''
2 '''begin'''
3 '''for''' j : = 1 '''to''' ''C''
4 '''begin'''
5 '''if''' ( i ≠ j ) '''then'''
6 '''begin'''
7 '''if''' ( d[i,j] > d[j,i] ) '''then'''
8 '''begin'''
9 p[i,j] : = d[i,j]
10 '''end'''
11 '''else'''
12 '''begin'''
13 p[i,j] : = 0
14 '''end'''
15 '''end'''
16 '''end'''
17 '''end'''
18
19 '''for''' i : = 1 '''to''' ''C''
20 '''begin'''
21 '''for''' j : = 1 '''to''' ''C''
22 '''begin'''
23 '''if''' ( i ≠ j ) '''then'''
24 '''begin'''
25 '''for''' k : = 1 '''to''' ''C''
26 '''begin'''
27 '''if''' ( i ≠ k ) '''then'''
28 '''begin'''
29 '''if''' ( j ≠ k ) '''then'''
30 '''begin'''
31 p[j,k] : = max { p[j,k]; min { p[j,i]; p[i,k] } }
32 '''end'''
33 '''end'''
34 '''end'''
35 '''end'''
36 '''end'''
37 '''end'''
38
39 '''for''' i : = 1 '''to''' ''C''
40 '''begin'''
41 winner[i] : = true
42 '''end'''
43
44 '''for''' i : = 1 '''to''' ''C''
45 '''begin'''
46 '''for''' j : = 1 '''to''' ''C''
47 '''begin'''
48 '''if''' ( i ≠ j ) '''then'''
49 '''begin'''
50 '''if''' ( p[j,i] > p[i,j] ) '''then'''
51 '''begin'''
52 winner[i] : = false
53 '''end'''
54 '''end'''
55 '''end'''
56 '''end'''
▲=== Examples ===
▲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 ====
Line 511 ⟶ 563:
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.
== Satisfied Criteria ==
Line 547 ⟶ 595:
# [[Favorite Betrayal criterion]]
# [[Later-no-harm criterion]]
== History of the Schulze method ==
The Schulze method was developed by Markus Schulze in 1997. The first time that the Schulze method was discussed in a public mailing list was in 1998 [http://lists.electorama.com/pipermail/election-methods-electorama.com/1998-July/001856.html] [http://lists.electorama.com/pipermail/election-methods-electorama.com/1998-August/001958.html] [http://lists.electorama.com/pipermail/election-methods-electorama.com/1998-August/002044.html] [http://lists.electorama.com/pipermail/election-methods-electorama.com/1998-September/002055.html] [http://lists.electorama.com/pipermail/election-methods-electorama.com/1998-November/002771.html]. In the following years, the Schulze method has been adopted e.g. by "Software in the Public Interest" (2003), Debian (2003), Gentoo (2005), TopCoder (2005), and "Sender Policy Framework" (2005). The first books on the Schulze method were written by Tideman (2006) and by Stahl and Johnson (2007).
== Use of the Schulze method ==
| |||