Die Schulze-Methode (nach Markus Schulze) ist die derzeit am weitesten verbreitete Condorcet-Methode.
Definition
Anzahl der Wähler
Die Anzahl der Wähler, die den Kandidat A dem Kandidat B 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 Kandidat B dem Kandidat A vorziehen.
- d[A,B] d[B,A]
Der Concordet-Sieger
Existieren mehrere Kandidaten, und gibt es einen Kandidaten y der allen anderen Kandidaten y vorgezogen wird, so ist dieser ein Concordet-Sieger.
- d[x,y] > d[y,x] für jeden zu Kandidat x unterscheidbaren Kandidat 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 Concordet-Sieger
Stärke eines Sieges
Angenommen, S[X,Y] ist die Stärke des Sieges von Kandidat X über Kandidat Y.
Beispiel 1 (margin):
- S[C,D] > S[E,F], dann und nur dann wenn d[C,D] - d[D,C] > d[E,F] - d[F,E].
Beispiel 2 (ratio):
- S[C,D] > S[E,F], dann und nur dann wenn mindestens eine der folgenden Bedingungen erfüllt ist:
- d[C,D] d[F,E] > d[D,C] d[E,F].
- d[C,D] = 0 und d[E,F] = 0 und d[D,C] < d[F,E].
- d[D,C] = 0 und d[F,E] = 0 und d[C,D] > d[E,F].
- d[C,D] = 0 und d[D,C] = 0 und d[E,F] < d[F,E].
- d[E,F] = 0 und d[F,E] = 0 und d[C,D] > d[D,C].
Beispiel 3 (winning votes):
- S1[X,Y] : = d[X,Y], falls d[X,Y] > d[Y,X].
- S1[X,Y] : = 0, falls d[X,Y] ≤ d[Y,X].
- S2[X,Y] : = d[X,Y] - d[Y,X].
- S[C,D] > S[E,F], dann und nur dann wenn mindestens eine der folgenden Bedingungen erfüllt ist:
- S1[C,D] > S1[E,F].
- S1[C,D] = S1[E,F] und S2[C,D] > S2[E,F].
Formulierung 1
Die Schulze-Methode ist folgendermaßen definiert:
- Ein Weg (path) von Kandidat X nach Kandidat Y der Stärke p 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): S[C(i),C(i+1)] ≥ p.
- Gibt es einen Weg vom Kandidaten A zum Kandidaten B der Stärke p und gibt es keinen Weg vom Kandidaten B zum Kandidaten A der Stärke p, dann wird Kandidat B mit der Wahrscheinlichkeit 0 gewählt.
Es läßt sich zeigen, daß die Stärken der Wege stets transitiv sind. Das heißt: Es existiert stets mindestens ein Kandidat, der nicht gemäß der obigen Regel disqualifiziert wird.
Ferner läßt sich zeigen, daß, sofern es keine paarweisen Siege CD und EF mit exakt gleicher Stärke S[C,D] = S[E,F] gibt, es stets exakt einen Kandidaten gibt, der gemäß der obigen Regel nicht disqualifiziert wird.
Formulierung 2
Alternativ läßt sich die Schulze-Methode folgendermaßen beschreiben:
- Ein Weg (path) von Kandidat X nach Kandidat 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.
- Die Stärke des Weges C(1),...,C(n) ist min { S[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 { S[C(i),C(i+1)] | i = 1,...,(n-1) } | C(1),...,C(n) ist ein Weg von Kandidat A nach Kandidat B }.
- Mit anderen Worten: p[A,B] ist die Stärke des stärksten Weges von Kandidat A nach Kandidat B.
- Kandidat A ist ein potentieller Sieger, dann und nur dann wenn p[A,B] ≥ p[B,A] ist für jeden anderen Kandidaten B.
Es läßt sich zeigen, daß es stets mindestens einen potentiellen Sieger gibt.
Ferner läßt sich zeigen, daß, sofern es keine paarweisen Siege CD und EF mit exakt gleicher Stärke S[C,D] = S[E,F] gibt, es stets exakt einen potentiellen Sieger gibt.
Ferner läßt sich zeigen, daß mit Hilfe des Dijkstra-Algorithmus' oder des Floyd-Warshall-Algorithmus' in einer Laufzeit von O(N^3) sämtliche p[X,Y] berechnet werden können, wobei N die Anzahl der Kandidaten ist.
Beispiele
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 |
Wenn alle Wähler ein komplettes Ranking abgeben, sind alle Definitionen für die Stärke eines paarweisen Sieges äquivalent. Wir können also o.B.d.A. annehmen, daß die Stärke eines paarweisen Sieges über winning votes definiert ist.
| ... 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.
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)
Unterschiedliche Heuristiken
Es existieren zahlreiche Heuristiken für die Schulze-Methode. Aus Gründen der Einfachheit wird in diesem Artikel jedoch nur die Wege-Heuristik benutzt.
Angenommen, d[X,Y] ist die Anzahl der Wähler, die den Kandidaten X dem Kandidaten Y strikt vorziehen. In der graphentheoretischen Interpretation von Wahlen ist dann S(d[X,X],d[Y,X]) das Gewicht des Bogens vom Knoten X zum Knoten Y.
Wege-Heuristik
Grundidee der Wege-Heuristik ("beatpath method", "beatpath winner", "path voting", "path winner", "strong immunity from binary arguments") ist, daß die Stärke des indirekten Vergleiches "Kandidat A vs. Kandidat B" die Stärke p[A,B] des stärksten gerichteten Weges A = C(1), ..., C(n) = B vom Kandidaten A zum Kandidaten B ist und daß die Stärke eines Weges die Stärke seines schwächsten Sieges ist.
Schwartz-Heuristik
Bei der Schwartz-Heuristik ("Schwartz Sequential Dropping", "Cloneproof Schwartz Sequential Dropping") werden in jedem Schritt zunächst der Schwartz-Set berechnet und alle Kandidaten, die sich nicht in diesem Set befinden, eliminiert und anschließend der schwächste paarweise Sieg durch eine paarweise Stimmengleichheit ersetzt. Dies wird so lange wiederholt, bis entweder nur noch ein einziger Kandidat übriggeblieben ist oder alle paarweisen Siege durch paarweise Stimmengleichheiten ersetzt worden sind.
Baum-Heuristik
Bei der Baum-Heuristik ("sequential dropping towards a spanning tree") wird der gerichtete spannende Baum (arborescence) berechnet, bei dem der Vektor, in dem die Gewichte der Bögen in aufsteigender Reihenfolge sortiert worden sind, lexikographisch maximal ist. Der Sieger ist die Wurzel dieses gerichteten Baumes.
Anwendungen
Die Schulze-Methode wird derzeit nicht in öffentlichen Wahlen angewandt. Sie findet jedoch mehr und mehr Anwendung in Privatorganisationen.
Weblinks
Artikel (alle englisch):
- A New Monotonic and Clone-Independent Single-Winner Election Method (PDF) von Markus Schulze
- 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 (wo die Methode "path winner" genannt wird)
- The Debian Voting System von Jochen Voss (wo die Schulze-Methode "CSSD" genannt wird)
- A Survey of Basic Voting Methods by James Green-Armytage (wo die Methode "SSD", "CSSD" und "beatpath" genannt wird)
- Single-Winner Methods von Mike Ossipoff (wo die Methode "SSD", "CSSD" und "beatpath winner" genannt wird)
- Accurate Democracy von Rob Loring (wo die Methode "SSD" and "beatpath" genannt wird)
- 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 (wo die Methode "beatpath winner" genannt wird)
- Condorcet Voting Calculator von Eric Gorr (wo die Schulze-Methode "beatpath winner" genannt wird)
- BetterPolls.com von Brian Olson (wo die Methode "beatpath" genannt wird)
- A different way to vote von Anguo Ma (wo die Methode "beatpath" genannt wird)
- Voting Software Project von Blake Cretney
- Condorcet with Dual Dropping Perl Scripts von Mathew Goldstein