Zum Inhalt springen

Schulze-Methode

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 25. März 2026 um 10:11 Uhr durch imported>Polluks (Beispiel einer Implementierung in Pascal: Pascal-like).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Die Schulze-Methode (nach Markus Schulze) ist ein Wahlverfahren aus der Familie der Vorzugswahlen, mit dem ein einzelner Sieger bestimmt wird. Es ist die derzeit verbreitetste Methode, um Wahlen durchzuführen, bei welchen der Wähler Kandidaten nach Rang ordnet.

Die Schulze-Methode ist eine Condorcet-Methode, d. h., dass sie einen Kandidaten, der im paarweisen Vergleich jeden anderen Kandidaten besiegen würde, als Sieger auswählt, sofern ein solcher existiert.

Markus Schulze hat die Methode 1997 entwickelt. Die ersten Veröffentlichungen datieren von 2003 und 2006.<ref>Condorcet sub-cycle rule, Election-Methods-Mailingliste, 3. Oktober 1997</ref><ref>Markus Schulze: A new monotonic and clone-independent single-winner election method. (PDF; 75 kB) In: Voting Matters, issue 17, 2003, S. 9–19</ref><ref>Nicolaus Tideman: Collective Decisions and Voting: The Potential for Public Choice. Ashgate Publishing, 2006. Saul Stahl, Paul E. Johnson: Understanding Modern Mathematics. Jones & Bartlett Publishing, 2006</ref> Verwendet wurde die Schulze-Methode erstmals 2003 (von Software in the Public Interest), 2003 (von Debian) und 2005 (von Gentoo Linux).

Erklärung

Jeder Wähler erhält eine komplette Liste aller Kandidaten. Er reiht die Kandidaten, indem er ihnen Zahlen zuordnet. Eine kleine Zahl ist besser als eine größere, jedoch zählt nur die Reihenfolge. Kandidaten mit gleicher Zahl sind an gleicher Stelle gereiht. Kandidaten ohne Zahl sind gemeinsam an letzter Stelle – so als ob der Wähler ihnen jeweils die größtmögliche Zahl zugeschrieben hätte.

Anzahl der Wähler

Die Anzahl der Wähler, die den Kandidaten <math>A</math> dem Kandidaten <math>B</math> vorziehen (d. h. die bei <math>A</math> eine kleinere Zahl als bei <math>B</math> vermerkt haben), wird durch <math>d[A,B]</math> ausgedrückt.

Der Wert von <math>d</math> wird aus den Stimmabgaben gezählt

  • <math>d[A,B]</math> ist die Zahl der Wähler, die Kandidaten <math>A</math> besser als <math>B</math> finden.
  • <math>d[B,A]</math> ist die Zahl der Wähler, die Kandidaten <math>B</math> besser als <math>A</math> finden.

Für diese Werte ist es unerheblich, ob noch andere Kandidaten existieren und ob diese besser oder schlechter als <math>A</math> und <math>B</math> oder zwischen beiden eingestuft werden.

Definition

Die Schulze-Methode ist folgendermaßen definiert:

Ein Weg ({{Modul:Vorlage:lang}} Modul:Vorlage:lang:103: attempt to index field 'wikibase' (a nil value)) vom Kandidaten <math>X</math> zum Kandidaten <math>Y</math> der Stärke <math>z</math> ist eine Sequenz von Kandidaten <math>C_1,\dots,C_n</math> mit den folgenden Eigenschaften:
  1. <math>C_1 = X</math>, d. h. der Weg beginnt bei <math>X</math>.
  2. <math>C_n = Y</math>, d. h. der Weg endet bei <math>Y</math>.
  3. <math>\forall i < n.\ d[C_i,C_{i+1}] > d[C_{i+1},C_i]</math>, d. h. jeder Kandidat auf dem Weg gewinnt den paarweisen Vergleich gegen den auf ihn folgenden Kandidaten.
  4. <math>\forall i < n.\ d[C_i,C_{i+1}] \geq z</math>, d. h. jeder Kandidat auf dem Weg wird gegenüber dem auf ihn folgenden Kandidaten von mindestens <math>z</math> Wählern bevorzugt.
  5. <math>\exists i < n.\ d[C_i,C_{i+1}] = z</math>, d. h. wenigstens einer dieser Vergleiche wird von (nur) genau <math>z</math> Wählern gestützt.
Hat ein Weg <math>C_1,\dots,C_n</math> die Stärke <math>z</math>, so werden die Bögen dieses Weges, für die <math>d[C_i,C_{i+1}] = z</math> gilt, kritische Siege genannt. Bei ihnen handelt es sich um die schwächsten Siege auf dem Weg.
<math>p[A,B]</math>, die Stärke des stärksten Weges vom Kandidaten <math>A</math> zum Kandidaten <math>B</math>, ist der größte Wert, so dass es einen Weg dieser Stärke vom Kandidaten <math>A</math> zum Kandidaten <math>B</math> gibt. Falls es überhaupt keinen Weg von <math>A</math> nach <math>B</math> gibt, wird <math>p[A,B] = 0</math> gesetzt.
Kandidat <math>A</math> ist besser als Kandidat <math>B</math> genau dann, wenn <math>p[A,B] > p[B,A]</math> ist.
Kandidat <math>A</math> ist ein potentieller Sieger genau dann, wenn <math>p[A,B] \ge p[B,A]</math> ist für jeden anderen Kandidaten <math>B</math>.

Es lässt sich zeigen, dass die besser-Relation transitiv ist. Es existiert somit stets mindestens ein potentieller Sieger.

Beispiel 1

1 <math>A</math> <math>A</math> <math>B</math> <math>C</math> <math>C</math> <math>C</math> <math>D</math> <math>E</math>
2 <math>C</math> <math>D</math> <math>E</math> <math>A</math> <math>A</math> <math>B</math> <math>C</math> <math>B</math>
3 <math>B</math> <math>E</math> <math>D</math> <math>B</math> <math>E</math> <math>A</math> <math>E</math> <math>A</math>
4 <math>E</math> <math>C</math> <math>A</math> <math>E</math> <math>B</math> <math>D</math> <math>B</math> <math>D</math>
5 <math>D</math> <math>B</math> <math>C</math> <math>D</math> <math>D</math> <math>E</math> <math>A</math> <math>C</math>
<math>5</math> <math>5</math> <math>8</math> <math>3</math> <math>7</math> <math>2</math> <math>7</math> <math>8</math>

Paarweise Matrix

Tabelle, die jeden Kandidaten mit jedem anderen vergleicht. Die rot markierten Felder werden weiter benutzt. Z. B. wurde Kandidat <math>B</math> von <math>25</math> Stimmen gegenüber <math>A</math> bevorzugt.

<math>d[\ast,A]</math> <math>d[\ast,B]</math> <math>d[\ast,C]</math> <math>d[\ast,D]</math> <math>d[\ast,E]</math>
<math>d[A,\ast]</math> 20 26 30 22
<math>d[B,\ast]</math> 25 16 33 18
<math>d[C,\ast]</math> 19 29 17 24
<math>d[D,\ast]</math> 15 12 28 14
<math>d[E,\ast]</math> 23 27 21 31

Paarweiser Graph

Graph mit gewichteten Pfeilen aus der Tabelle von oben. Man sieht den Pfeil von Kandidat <math>B</math> zu Kandidat <math>A</math> mit dem Gewicht von <math>25</math> aus der obigen Tabelle.

Paarweiser Graph

Die stärksten Wege

Von den Verbindungen zwischen Kandidaten wird diejenige gesucht, bei der das schwächste Glied am stärksten ist. Bildlich gesprochen wird die stärkste Kette gesucht. Wie kommt man von <math>A</math> nach <math>B</math>?

  • Bei <math>A</math> über <math>C</math> nach <math>B</math> ist das schwächste Glied von <math>A</math> nach <math>C</math> mit <math>26</math>.
  • Bei <math>A</math> über <math>D</math> und <math>C</math> nach <math>B</math> ist das schwächste Glied <math>D</math> nach <math>C</math> mit <math>28</math>. Diese Kette ist stärker und <math>28</math> wird nachfolgend verwendet.

Man kann sich den Vorgang beispielsweise aus Sicht eines Transportunternehmens vorstellen, das möglichst viele Pakete auf einmal von einer Stadt in die andere transportieren möchte (egal wie lang der Weg ist). Ohne Zwischenlager kann natürlich nur so viel transportiert werden wie das Fassungsvermögen des kleinsten Transportmittels, das am Weg verwendet wird: Wenn die Pakete zuerst per Fähre, dann per Lastkraftwagen und zuletzt per Güterzug transportiert werden, dann ist wahrscheinlich der Lastkraftwagen am kleinsten. Im Vergleich zu einer anderen Route (die z. B. einen Pickup-Truck enthält) ist der Lastkraftwagen damit das schwächste Glied der stärksten Kette.

Oft wird dieses schwächste Glied der stärksten Kette auch kritischer Sieg genannt. Die kritischen Siege der stärksten Wege sind unterstrichen.

… nach <math>A</math> … nach <math>B</math> … nach <math>C</math> … nach <math>D</math> … nach <math>E</math>
von <math>A</math> …
A–(30)–D–(28)–C–(29)–B
A–(30)–D–(28)–C–(29)–B

<math>A\overset{30}\longrightarrow D\overset{\underline{28}}\longrightarrow C\overset{29}\longrightarrow B</math>

A–(30)–D–(28)–C
A–(30)–D–(28)–C

<math>A\overset{30}\longrightarrow D\overset{\underline{28}}\longrightarrow C</math>

A–(30)–D
A–(30)–D

<math>A\overset{\underline{30}}\longrightarrow D</math>

A–(30)–D–(28)–C–(24)–E
A–(30)–D–(28)–C–(24)–E

<math>A\overset{30}\longrightarrow D\overset{28}\longrightarrow C\overset{\underline{24}}\longrightarrow E</math>

von <math>B</math> …
B–(25)–A
B–(25)–A

<math>B\overset{\underline{25}}\longrightarrow A</math>

B–(33)–D–(28)–C
B–(33)–D–(28)–C

<math>B\overset{33}\longrightarrow D\overset{\underline{28}}\longrightarrow C</math>

B-(33)-D
B-(33)-D

<math>B\overset{\underline{33}}\longrightarrow D</math>

B-(33)-D-(28)-C-(24)-E
B-(33)-D-(28)-C-(24)-E

<math>B\overset{33}\longrightarrow D\overset{28}\longrightarrow C\overset{\underline{24}}\longrightarrow E</math>

von <math>C</math> …
C-(29)-B-(25)-A
C-(29)-B-(25)-A

<math>C\overset{29}\longrightarrow B\overset{\underline{25}}\longrightarrow A</math>

C-(29)-B
C-(29)-B

<math>C\overset{\underline{29}}\longrightarrow B</math>

C-(29)-B-(33)-D
C-(29)-B-(33)-D

<math>C\overset{\underline{29}}\longrightarrow B\overset{33}\longrightarrow D</math>

C-(24)-E
C-(24)-E

<math>C\overset{\underline{24}}\longrightarrow E</math>

von <math>D</math> …
D-(28)-C-(29)-B-(25)-A
D-(28)-C-(29)-B-(25)-A

<math>D\overset{28}\longrightarrow C\overset{29}\longrightarrow B\overset{\underline{25}}\longrightarrow A</math>

D-(28)-C-(29)-B
D-(28)-C-(29)-B

<math>D\overset{\underline{28}}\longrightarrow C\overset{29}\longrightarrow B</math>

D-(28)-C
D-(28)-C

<math>D\overset{\underline{28}}\longrightarrow C</math>

D-(28)-C-(24)-E
D-(28)-C-(24)-E

<math>D\overset{28}\longrightarrow C\overset{\underline{24}}\longrightarrow E</math>

von <math>E</math> …
E-(31)-D-(28)-C-(29)-B-(25)-A
E-(31)-D-(28)-C-(29)-B-(25)-A

<math>E\overset{31}\longrightarrow D\overset{28}\longrightarrow C\overset{29}\longrightarrow B\overset{\underline{25}}\longrightarrow A</math>

E-(31)-D-(28)-C-(29)-B
E-(31)-D-(28)-C-(29)-B

<math>E\overset{31}\longrightarrow D\overset{\underline{28}}\longrightarrow C\overset{29}\longrightarrow B</math>

E-(31)-D-(28)-C
E-(31)-D-(28)-C

<math>E\overset{31}\longrightarrow D\overset{\underline{28}}\longrightarrow C</math>

E-(31)-D
E-(31)-D

<math>E\overset{\underline{31}}\longrightarrow D</math>

Die Stärken der stärksten Wege

Das schwächste Glied der stärksten Verbindung, wie oben gefunden, wird in eine Tabelle eingetragen. Dann wird wieder paarweise verglichen, wer wen schlägt, in der Tabelle unten wieder rot markiert.

<math>p[\ast,A]</math> <math>p[\ast,B]</math> <math>p[\ast,C]</math> <math>p[\ast,D]</math> <math>p[\ast,E]</math>
<math>p[A,\ast]</math> 28 28 30 24
<math>p[B,\ast]</math> 25 28 33 24
<math>p[C,\ast]</math> 25 29 29 24
<math>p[D,\ast]</math> 25 28 28 24
<math>p[E,\ast]</math> 25 28 28 31

Ergebnis

Sieger nach der Schulze-Methode ist Kandidat <math>E</math>, da <math>p[E,X] \ge p[X,E]</math> ist für jeden anderen Kandidaten <math>X</math>.

  • Wegen <math>25 = p[E,A] > p[A,E] = 24</math> ist Kandidat <math>E</math> besser als Kandidat <math>A</math>.
  • Wegen <math>28 = p[E,B] > p[B,E] = 24</math> ist Kandidat <math>E</math> besser als Kandidat <math>B</math>.
  • Wegen <math>28 = p[E,C] > p[C,E] = 24</math> ist Kandidat <math>E</math> besser als Kandidat <math>C</math>.
  • Wegen <math>31 = p[E,D] > p[D,E] = 24</math> ist Kandidat <math>E</math> besser als Kandidat <math>D</math>.
  • Wegen <math>28 = p[A,B] > p[B,A] = 25</math> ist Kandidat <math>A</math> besser als Kandidat <math>B</math>.
  • Wegen <math>28 = p[A,C] > p[C,A] = 25</math> ist Kandidat <math>A</math> besser als Kandidat <math>C</math>.
  • Wegen <math>30 = p[A,D] > p[D,A] = 25</math> ist Kandidat <math>A</math> besser als Kandidat <math>D</math>.
  • Wegen <math>29 = p[C,B] > p[B,C] = 28</math> ist Kandidat <math>C</math> besser als Kandidat <math>B</math>.
  • Wegen <math>29 = p[C,D] > p[D,C] = 28</math> ist Kandidat <math>C</math> besser als Kandidat <math>D</math>.
  • Wegen <math>33 = p[B,D] > p[D,B] = 28</math> ist Kandidat <math>B</math> besser als Kandidat <math>D</math>.

Das Schulze-Ranking ist somit <math>E > A > C > B > D</math>.

Beispiel 2

1 <math>A</math> <math>D</math> <math>D</math> <math>C</math>
2 <math>B</math> <math>A</math> <math>B</math> <math>B</math>
3 <math>C</math> <math>B</math> <math>C</math> <math>D</math>
4 <math>D</math> <math>C</math> <math>A</math> <math>A</math>
<math>3</math> <math>2</math> <math>2</math> <math>2</math>

Paarweise Matrix

<math>d[\ast,A]</math> <math>d[\ast,B]</math> <math>d[\ast,C]</math> <math>d[\ast,D]</math>
<math>d[A,\ast]</math> 5 5 3
<math>d[B,\ast]</math> 4 7 5
<math>d[C,\ast]</math> 4 2 5
<math>d[D,\ast]</math> 6 4 4

Paarweiser Graph

Datei:Schulze method example4.svg

Die stärksten Wege

Die kritischen Siege der stärksten Wege sind unterstrichen.

… nach <math>A</math> … nach <math>B</math> … nach <math>C</math> … nach <math>D</math>
von <math>A</math> …
Datei:Schulze method example4 AB.svg

<math>A\overset{\underline{5}}\longrightarrow B</math>

Datei:Schulze method example4 AC.svg

<math>A\overset{\underline{5}}\longrightarrow C</math>

Datei:Schulze method example4 AD.svg

<math>A\overset{\underline{5}}\longrightarrow B\overset{\underline{5}}\longrightarrow D</math>

von <math>B</math> …
Datei:Schulze method example4 BA.svg

<math>B\overset{\underline{5}}\longrightarrow D\overset{6}\longrightarrow A</math>

Datei:Schulze method example4 BC.svg

<math>B\overset{\underline{7}}\longrightarrow C</math>

Datei:Schulze method example4 BD.svg

<math>B\overset{\underline{5}}\longrightarrow D</math>

von <math>C</math> …
Datei:Schulze method example4 CA.svg

<math>C\overset{\underline{5}}\longrightarrow D\overset{6}\longrightarrow A</math>

Datei:Schulze method example4 CB.svg

<math>C\overset{\underline{5}}\longrightarrow D\overset{6}\longrightarrow A\overset{\underline{5}}\longrightarrow B</math>

Datei:Schulze method example4 CD.svg

<math>C\overset{\underline{5}}\longrightarrow D</math>

von <math>D</math> …
Datei:Schulze method example4 DA.svg

<math>D\overset{\underline{6}}\longrightarrow A</math>

Datei:Schulze method example4 DB.svg

<math>D\overset{6}\longrightarrow A\overset{\underline{5}}\longrightarrow B</math>

Datei:Schulze method example4 DC.svg

<math>D\overset{6}\longrightarrow A\overset{\underline{5}}\longrightarrow C</math>

Die Stärken der stärksten Wege

Das schwächste Glied der stärksten Verbindung wie oben gefunden, wird in eine Tabelle eingetragen. Dann wird wieder paarweise verglichen, wer wen schlägt, in der Tabelle unten wieder rot markiert. Violett markiert ist jeder Gleichstand.

<math>p[\ast,A]</math> <math>p[\ast,B]</math> <math>p[\ast,C]</math> <math>p[\ast,D]</math>
<math>p[A,\ast]</math> 5 5 5
<math>p[B,\ast]</math> 5 7 5
<math>p[C,\ast]</math> 5 5 5
<math>p[D,\ast]</math> 6 5 5

Ergebnis

Potentielle Sieger nach der Schulze-Methode sind somit Kandidat <math>B</math> und Kandidat <math>D</math>, da

<math>p[B,X] \ge p[X,B]</math> ist für jeden anderen Kandidaten <math>X</math> und
<math>p[D,Y] \ge p[Y,D]</math> ist für jeden anderen Kandidaten <math>Y</math>.

Wegen <math>7 = p[B,C] > p[C,B] = 5</math> ist Kandidat <math>B</math> besser als Kandidat <math>C</math>.

Wegen <math>6 = p[D,A] > p[A,D] = 5</math> ist Kandidat <math>D</math> besser als Kandidat <math>A</math>.

Mögliche Schulze-Rankings sind somit

  • <math>B > C > D > A</math>,
  • <math>B > D > A > C</math>,
  • <math>B > D > C > A</math>,
  • <math>D > A > B > C</math>,
  • <math>D > B > A > C</math> und
  • <math>D > B > C > A</math>.

Implementierung

Sei C die Anzahl der Kandidaten. Dann lassen sich die Stärken der stärksten Wege mit Hilfe des Algorithmus von Floyd und Warshall berechnen.

Input: d[i,j] ist die Anzahl der Wähler, die den Kandidaten i dem Kandidaten j strikt vorziehen.

Output: p[i,j] ist die Stärke des stärksten Weges vom Kandidaten i zum Kandidaten j.

Beispiel einer Implementierung in Pascal

<syntaxhighlight lang="pascal"> var i, j, k: 1..C;

for i := 1 to C do begin

  for j := 1 to C do
  begin
     if i <> j then
     begin
        if d[i,j] > d[j,i] then
        begin
           p[i,j] := d[i,j]
        end
        else
        begin
           p[i,j] := 0
        end
     end
  end

end

for i := 1 to C do begin

  for j := 1 to C do
  begin
     if i <> j then
     begin
        for k := 1 to C do
        begin
           if i <> k then
           begin
              if j <> k then
              begin
                 p[j,k] := max ( p[j,k], min ( p[j,i], p[i,k] ) )
              end
           end
        end
     end
  end

end </syntaxhighlight>

Heuristiken und Eigenschaften

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).

Die Schulze-Methode erfüllt die folgenden Kriterien<ref>Markus Schulze: A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method. (PDF; 1,4 MB) Juli 2007 (englisch)</ref><ref>D. R. Woodall: Properties of Preferential Election Rules. Dezember 1994 (englisch)</ref> (Zur Erläuterung der wichtigsten Kriterien siehe Abschnitt Qualitätskriterien im Artikel Sozialwahltheorie):

  1. Majority criterion
  2. Mutual majority criterion
  3. Monotonicity criterion (auch bezeichnet als non-negative responsiveness, mono-raise)
  4. Pareto criterion
  5. Condorcet-Kriterium
  6. Condorcet-Verlierer-Kriterium
  7. Smith criterion (auch bezeichnet als Generalized Condorcet criterion)
  8. Local independence from irrelevant alternatives
  9. Schwartz-Kriterium
  10. Strategy-Free criterion
  11. Generalized Strategy-Free criterion
  12. Strong Defensive Strategy criterion
  13. Weak Defensive Strategy criterion
  14. Summability criterion
  15. Independence of clones
  16. nicht-diktatorisch
  17. Universalität
  18. Woodall’s plurality criterion
  19. Woodall’s CDTT criterion
  20. Minimal Defense criterion
  21. Resolvability
  22. Reversal symmetry
  23. mono-append
  24. mono-add-plump

Die Schulze-Methode verletzt

  1. das Konsistenzkriterium,
  2. das Partizipationskriterium,
  3. die Unabhängigkeit von irrelevanten Alternativen
  4. sowie das Favorite-betrayal-Kriterium.

Anwendungen

Datei:Voting2.png
Muster für die elektronischen Stimmzettel für die Wahlen zum Kuratorium der Wikimedia Foundation

Die Schulze-Methode wird derzeit nicht in staatlichen Wahlen angewandt. Sie findet jedoch mehr und mehr Anwendung in Privatorganisationen. Sie ist u. a. in folgenden Organisationen benutzt worden:

Siehe auch

Literatur

Weblinks

Commons: Schulze method – Album mit Bildern, Videos und Audiodateien

Einzelnachweise

<references />