Die Schulze-Methode (nach Markus Schulze) ist die derzeit am weitesten verbreitete Condorcet-Methode. Spezielle Heuristiken der Schulze-Methode sind auch bekannt unter den Namen Beatpath, Beatpaths, Beatpath Method, Beatpath Winner, Path Voting, Path Winner, Schwartz Sequential Dropping (SSD) und Cloneproof Schwartz Sequential Dropping (CSSD).
Definition
Jeder Wähler erhält eine komplette Liste aller Kandidaten und nummeriert diese seinen Präferenzen entsprechend durch. Hierbei darf er dieselbe Präferenz an mehrere Kandidaten vergeben. Er darf auch Kandidaten auslassen. Wenn ein Wähler Kandidaten ausläßt, so wird dies so interpretiert, als ob dieser Wähler (1) all diejenigen Kandidaten, an die er eine Präferenz vergeben hat, all denjenigen Kandidaten, die er ausgelassen hat, strikt vorzieht und (2) indifferent zwischen all den ausgelassenen Kandidaten ist.
Anzahl der Wähler
Die Anzahl der Wähler, die den Kandidaten A dem Kandidaten B strikt vorziehen, wird durch d[A,B] ausgedrückt. Der Ausdruck d[A,B] ist nicht kommutativ, denn mit d[B,A] ist die Anzahl der Wähler gemeint, die den Kandidaten B dem Kandidaten A strikt vorziehen.
- d[A,B] d[B,A]
Der Condorcet-Sieger
Existieren mehrere Kandidaten, und gibt es einen Kandidaten x der allen anderen Kandidaten y strikt vorgezogen wird, so ist dieser ein Condorcet-Sieger.
- d[x,y] > d[y,x] für jeden zu Kandidat x unterscheidbaren Kandidaten y
Gegenbeispiel:
| Kandidat A | Kandidat B | Kandidat C | |
| Kandidat A | - | 70 | 33 |
| Kandidat B | 27 | - | 60 |
| Kandidat C | 64 | 35 | - |
Wie man der Tabelle entnehmen kann, wird in dem Beispiel jedem Kandidaten ein anderer Kandidat vorgezogen. Es existiert in diesem Beispiel also kein Condorcet-Sieger.
Formulierung
Die Schulze-Methode ist folgendermaßen definiert:
- Ein Weg (path) vom Kandidaten X zum Kandidaten Y der Stärke z ist ein geordneter Set von Kandidaten C(1),...,C(n) mit den folgenden Eigenschaften:
- C(1) ist identisch mit X.
- C(n) ist identisch mit Y.
- Für i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
- Für i = 1,...,(n-1): d[C(i),C(i+1)] ≥ z.
- Gibt es ein p, so daß es einen Weg vom Kandidaten A zum Kandidaten B der Stärke p gibt und es keinen Weg vom Kandidaten B zum Kandidaten A der Stärke p gibt, dann disqualifiziert der Kandidat A den Kandidaten B.
- Kandidat D ist ein potentieller Sieger, genau dann wenn es keinen Kandidaten E gibt, so daß der Kandidat E den Kandidaten D disqualifiziert.
Es läßt sich zeigen, daß es stets mindestens einen potentiellen Sieger gibt.
Beispiele
Ein Weg (path) vom Kandidaten X zum Kandidaten Y ist ein geordneter Set von Kandidaten C(1),...,C(n) mit den folgenden Eigenschaften:
- C(1) ist identisch mit X.
- C(n) ist identisch mit Y.
- Für i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
Die Stärke des Weges C(1),...,C(n) ist min { d[C(i),C(i+1)] | i = 1,...,(n-1) }.
Mit anderen Worten: Die Stärke eines Weges ist die Stärke seines schwächsten Sieges.
p[A,B] : = max { min { d[C(i),C(i+1)] | i = 1,...,(n-1) } | C(1),...,C(n) ist ein Weg vom Kandidaten A zum Kandidaten B }.
Mit anderen Worten: p[A,B] ist die Stärke des stärksten Weges vom Kandidaten A zum Kandidaten B.
Dann läßt sich die Schulze-Methode folgendermaßen beschreiben: Kandidat A ist ein potentieller Sieger, genau dann wenn p[A,B] ≥ p[B,A] ist für jeden anderen Kandidaten B.
Beispiel 1
Beispiel (45 Wähler; 5 Kandidaten):
- 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 |
Die kritischen Siege der stärksten Wege sind unterstrichen.
| ... nach A | ... nach B | ... nach C | ... nach D | ... nach E | |
|---|---|---|---|---|---|
| von A ... | A-(30)-D-(28)-C-(29)-B | A-(30)-D-(28)-C | A-(30)-D | A-(30)-D-(28)-C-(24)-E | |
| von B ... | B-(25)-A | B-(33)-D-(28)-C | B-(33)-D | B-(33)-D-(28)-C-(24)-E | |
| von C ... | C-(29)-B-(25)-A | C-(29)-B | C-(29)-B-(33)-D | C-(24)-E | |
| von D ... | D-(28)-C-(29)-B-(25)-A | D-(28)-C-(29)-B | D-(28)-C | D-(28)-C-(24)-E | |
| von 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 |
Sieger nach der Schulze-Methode ist Kandidat E, da p[E,X] ≥ p[X,E] ist für jeden anderen Kandidaten X.
Ranked Pairs hingegen
- schließt B > D (33:12),
- schließt E > D (31:14),
- schließt A > D (30:15),
- schließt C > B (29:16),
- überspringt D > C (28:17), da D > C einen gerichteten Kreis mit den bereits geschlossenen paarweisen Siegen C > B und B > D bilden würde,
- schließt E > B (27:18),
- schließt A > C (26:19),
- überspringt B > A (25:20), da B > A einen gerichteten Kreis mit den bereits geschlossenen paarweisen Siegen A > C und C > B bilden würde,
- schließt C > E (24:21),
- überspringt E > A (23:22), da E > A einen gerichteten Kreis mit den bereits geschlossenen paarweisen Siegen A > C und C > E bilden würde.
Der Sieger nach Ranked Pairs ist somit Kandidat A.
Beispiel 2
Beispiel (30 Wähler; 4 Kandidaten):
- 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 |
Die kritischen Siege der stärksten Wege sind unterstrichen.
| ... nach A | ... nach B | ... nach C | ... nach D | |
|---|---|---|---|---|
| von A ... | A-(20)-C-(21)-B | A-(20)-C | A-(20)-C-(17)-D | |
| von B ... | B-(19)-A | B-(19)-A-(20)-C | B-(19)-A-(20)-C-(17)-D | |
| von C ... | C-(21)-B-(19)-A | C-(21)-B | C-(17)-D | |
| von 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 |
Sieger nach der Schulze-Methode ist Kandidat D, da p[D,X] ≥ p[X,D] ist für jeden anderen Kandidaten X.
Ranked Pairs hingegen
- schließt C > B (21:9),
- schließt A > C (20:10),
- überspringt B > A (19:11), da B > A einen gerichteten Kreis mit den bereits geschlossenen paarweisen Siegen A > C und C > B bilden würde,
- schließt D > B (18:12),
- schließt C > D (17:13),
- überspringt D > A (16:14), da D > A einen gerichteten Kreis mit den bereits geschlossenen paarweisen Siegen A > C und C > D bilden würde.
Der Sieger nach Ranked Pairs ist somit Kandidat A.
Beispiel 3
Dieses Beispiel stammt von dieser Webseite.
Beispiel (30 Wähler; 5 Kandidaten):
- 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 |
Die kritischen Siege der stärksten Wege sind unterstrichen.
| ... nach A | ... nach B | ... nach C | ... nach D | ... nach E | |
|---|---|---|---|---|---|
| von A ... | A-(18)-B | A-(21)-D-(20)-C | A-(21)-D | A-(21)-E | |
| von 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 | |
| von C ... | C-(19)-A | C-(19)-A-(18)-B | C-(19)-A-(21)-D | C-(19)-A-(21)-E | |
| von D ... | D-(20)-C-(19)-A | D-(20)-C-(19)-A-(18)-B | D-(20)-C | D-(30)-E | |
| von 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 |
Sieger nach der Schulze-Methode ist Kandidat B, da p[B,X] ≥ p[X,B] ist für jeden anderen Kandidaten X.
Beispiel 4
Dieses Beispiel stammt aus diesem Paper (PDF).
Beispiel (9 Wähler; 4 Kandidaten):
- 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 |
Die kritischen Siege der stärksten Wege sind unterstrichen.
| ... nach A | ... nach B | ... nach C | ... nach D | |
|---|---|---|---|---|
| von A ... | A-(5)-B | A-(5)-C | A-(5)-C-(5)-D | |
| von B ... | B-(5)-D-(6)-A | B-(7)-C | B-(5)-D | |
| von C ... | C-(5)-D-(6)-A | C-(5)-D-(6)-A-(5)-B | C-(5)-D | |
| von 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 |
Potentielle Sieger nach der Schulze-Methode sind somit Kandidat B und Kandidat D, da (1) p[B,X] ≥ p[X,B] ist für jeden anderen Kandidaten X und (2) p[D,Y] ≥ p[Y,D] ist für jeden anderen Kandidaten Y.
Eigenschaften
Die Schulze-Methode erfüllt die folgenden Kriterien:
- Majority criterion
- Mutual majority criterion
- Monotonicity criterion (a.k.a. mono-raise)
- Pareto criterion
- Condorcet criterion (a.k.a. Condorcet winner criterion)
- Condorcet loser criterion
- Smith criterion (a.k.a. Generalized Condorcet criterion)
- Local independence from irrelevant alternatives
- Schwartz criterion
- Strategy-Free criterion
- Generalized Strategy-Free criterion
- Strong Defensive Strategy criterion
- Weak Defensive Strategy criterion
- Summability criterion
- Independence of clones (Siehe clones!)
- nicht-diktatorisch
- Universalität
- Woodall's plurality criterion
- Woodall's CDTT criterion
- Minimal Defense criterion
- Resolvability (Siehe Kapitel 5.3 dieses Papers (PDF)!)
- Reversal symmetry (Siehe Kapitel 5.5 dieses Papers (PDF)!)
- mono-append
- mono-add-plump
Die Schulze-Methode verletzt die folgenden Kriterien:
- alle Kriterien, die mit dem Condorcet-Kriterium unvereinbar sind (z.B. independence from irrelevant alternatives, participation, consistency, invulnerability to compromising, invulnerability to burying, Favorite Betrayal criterion, later-no-harm)
Anwendungen
Die Schulze-Methode wird derzeit nicht in öffentlichen Wahlen angewandt. Sie findet jedoch mehr und mehr Anwendung in Privatorganisationen. Derzeit wird sie in folgenden Organisationen benutzt:
- Wikipédia francophone (Siehe hier!)
- Debian (Siehe Anhang A6 der Verfassung!)
- Software in the Public Interest (SPI) [1]
- Gentoo Foundation [2] [3] [4] [5]
- League of Professional System Administrators (LOPSA) (Siehe Artikel 8.3 der Bylaws!)
- Sender Policy Framework (SPF) [6]
- Mathematical Knowledge Management Interest Group (MKM-IG) [7] [8] [9]
- Park Alumni Society (PAS) [10]
- Kingman Hall [11] [12]
- Blitzed [13]
- Democratic Experience (DemExp) (Siehe Kapitel 30.6 dieses Papers (PDF)!)
- TopCoder [14]
Weblinks
Originalliteratur
- A New Monotonic and Clone-Independent Single-Winner Election Method (PDF) von Markus Schulze
- A New Monotonic, Clone-Independent, Reversal Symmetric, and Condorcet-Consistent Single-Winner Election Method (PDF) von Markus Schulze
- Free Riding and Vote Management under Proportional Representation by the Single Transferable Vote (PDF) von Markus Schulze
Weiterführende Literatur
- Descriptions of ranked-ballot voting methods von Rob LeGrand
- Election Methods Resource von Blake Cretney
- Election Methods and Criteria von Kevin Venzke
- Election Systems (PDF) von Peter A. Taylor
- Voting Systems (PDF) von Paul E. Johnson
- The Maximize Affirmed Majorities voting procedure (MAM) von Steve Eppley
- The Debian Voting System von Jochen Voss
- A Survey of Basic Voting Methods von James Green-Armytage
- Single-Winner Methods von Mike Ossipoff
- Accurate Democracy von Rob Loring
- Social Choice Under Incomplete, Cyclic Preferences (PDF) von Jobst Heitzig (wo die Methode "strong immunity from binary arguments" genannt wird)
Software
- Condorcet Internet Voting Service (CIVS) von Andrew Myers
- Condorcet Voting Calculator von Eric Gorr
- BetterPolls.com von Brian Olson
- A different way to vote von Anguo Ma
- Voting Software Project von Blake Cretney
- Condorcet with Dual Dropping Perl Scripts von Mathew Goldstein
- Haskell Condorcet Module von Evan Martin