imported>Polluks: /* Beispiel einer Implementierung in Pascal */ Pascal-like

2026-03-25T10:11:28Z

Beispiel einer Implementierung in Pascal: Pascal-like

Neue Seite

Die '''Schulze-Methode''' (nach Markus Schulze) ist ein [[Wahlsystem|Wahlverfahren]] aus der Familie der [[Vorzugswahl]]en, 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>[http://lists.electorama.com/pipermail/election-methods-electorama.com/1997-October/001570.html Condorcet sub-cycle rule], Election-Methods-Mailingliste, 3. Oktober 1997</ref><ref>Markus Schulze: [http://www.votingmatters.org.uk/ISSUE17/I17P3.PDF ''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 [[Kandidat]]en. 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'' ({{enS|path}}) 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:

:# <math>C_1 = X</math>, d. h. der Weg beginnt bei <math>X</math>.
:# <math>C_n = Y</math>, d. h. der Weg endet bei <math>Y</math>.
:# <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.
:# <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.
:# <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 [[Transitive Relation|transitiv]] ist. Es existiert somit stets mindestens ein potentieller Sieger.

=== Beispiel 1 ===

{| class="wikitable hintergrundfarbe-basis" style="border: 0; text-align: center;"
|-
! 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>
|-
|style="border-bottom:0; border-left:0;"|
! style="width:30px"| <math>5</math>
! style="width:30px"| <math>5</math>
! style="width:30px"| <math>8</math>
! style="width:30px"| <math>3</math>
! style="width:30px"| <math>7</math>
! style="width:30px"| <math>2</math>
! style="width:30px"| <math>7</math>
! style="width:30px"| <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.

{| class="wikitable hintergrundfarbe-basis" style="border:0; text-align:center;"
|-
|style="border-top:0; border-left:0;"|
|class="hintergrundfarbe5"| <math>d[\ast,A]</math>
|class="hintergrundfarbe5"| <math>d[\ast,B]</math>
|class="hintergrundfarbe5"| <math>d[\ast,C]</math>
|class="hintergrundfarbe5"| <math>d[\ast,D]</math>
|class="hintergrundfarbe5"| <math>d[\ast,E]</math>
|-
|class="hintergrundfarbe5"| <math>d[A,\ast]</math>
|class="hintergrundfarbe5"| || 20 ||style="background:#FEDBCA; color:#202122;"| 26 ||style="background:#FEDBCA; color:#202122;"|30 || 22
|-
|class="hintergrundfarbe5"| <math>d[B,\ast]</math>
|style="background:#FEDBCA; color:#202122;"| 25 ||class="hintergrundfarbe5"| || 16 ||style="background:#FEDBCA; color:#202122;"|33 || 18
|-
|class="hintergrundfarbe5"| <math>d[C,\ast]</math>
| 19 ||style="background:#FEDBCA; color:#202122;"| 29 ||class="hintergrundfarbe5"| || 17 ||style="background:#FEDBCA; color:#202122;"| 24
|-
|class="hintergrundfarbe5"| <math>d[D,\ast]</math>
| 15 || 12 ||style="background:#FEDBCA; color:#202122;"| 28 ||class="hintergrundfarbe5"| || 14
|-
|class="hintergrundfarbe5"| <math>d[E,\ast]</math>
|style="background:#FEDBCA; color:#202122;"| 23 ||style="background:#FEDBCA; color:#202122;"| 27 || 21 ||style="background:#FEDBCA; color:#202122;"|31 ||class="hintergrundfarbe5"|
|}

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

[[Datei:Schulze method example1.svg|rahmenlos|hochkant=1.1|klasse=skin-invert|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 [[Pick-up|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.

{| class="wikitable hintergrundfarbe-basis skin-invert-image" style="border: 0; text-align: center;"
|-
|style="border-top:0; border-left:0;"|
|class="hintergrundfarbe5"| … nach <math>A</math>
|class="hintergrundfarbe5"| … nach <math>B</math>
|class="hintergrundfarbe5"| … nach <math>C</math>
|class="hintergrundfarbe5"| … nach <math>D</math>
|class="hintergrundfarbe5"| … nach <math>E</math>
|-
|class="hintergrundfarbe5"| von <math>A</math> …
|class="hintergrundfarbe5"|
| [[Datei:Schulze method example1 AB.svg|ohne|150px|A–(30)–D–(28)–C–(29)–B]]
<math>A\overset{30}\longrightarrow D\overset{\underline{28}}\longrightarrow C\overset{29}\longrightarrow B</math>
| [[Datei:Schulze method example1 AC.svg|ohne|150px|A–(30)–D–(28)–C]]
<math>A\overset{30}\longrightarrow D\overset{\underline{28}}\longrightarrow C</math>
| [[Datei:Schulze method example1 AD.svg|ohne|150px|A–(30)–D]]
<math>A\overset{\underline{30}}\longrightarrow D</math>
| [[Datei:Schulze method example1 AE.svg|ohne|150px|A–(30)–D–(28)–C–(24)–E]]
<math>A\overset{30}\longrightarrow D\overset{28}\longrightarrow C\overset{\underline{24}}\longrightarrow E</math>
|-
|class="hintergrundfarbe5"| von <math>B</math> …
| [[Datei:Schulze method example1 BA.svg|ohne|150px|B–(25)–A]]
<math>B\overset{\underline{25}}\longrightarrow A</math>
|class="hintergrundfarbe5"|
| [[Datei:Schulze method example1 BC.svg|ohne|150px|B–(33)–D–(28)–C]]
<math>B\overset{33}\longrightarrow D\overset{\underline{28}}\longrightarrow C</math>
| [[Datei:Schulze method example1 BD.svg|ohne|150px|B-(33)-D]]
<math>B\overset{\underline{33}}\longrightarrow D</math>
| [[Datei:Schulze method example1 BE.svg|ohne|150px|B-(33)-D-(28)-C-(24)-E]]
<math>B\overset{33}\longrightarrow D\overset{28}\longrightarrow C\overset{\underline{24}}\longrightarrow E</math>
|-
|class="hintergrundfarbe5"| von <math>C</math> …
| [[Datei:Schulze method example1 CA.svg|ohne|150px|C-(29)-B-(25)-A]]
<math>C\overset{29}\longrightarrow B\overset{\underline{25}}\longrightarrow A</math>
| [[Datei:Schulze method example1 CB.svg|ohne|150px|C-(29)-B]]
<math>C\overset{\underline{29}}\longrightarrow B</math>
|class="hintergrundfarbe5"|
| [[Datei:Schulze method example1 CD.svg|ohne|150px|C-(29)-B-(33)-D]]
<math>C\overset{\underline{29}}\longrightarrow B\overset{33}\longrightarrow D</math>
| [[Datei:Schulze method example1 CE.svg|ohne|150px|C-(24)-E]]
<math>C\overset{\underline{24}}\longrightarrow E</math>
|-
|class="hintergrundfarbe5"| von <math>D</math> …
| [[Datei:Schulze method example1 DA.svg|ohne|150px|D-(28)-C-(29)-B-(25)-A]]
<math>D\overset{28}\longrightarrow C\overset{29}\longrightarrow B\overset{\underline{25}}\longrightarrow A</math>
| [[Datei:Schulze method example1 DB.svg|ohne|150px|D-(28)-C-(29)-B]]
<math>D\overset{\underline{28}}\longrightarrow C\overset{29}\longrightarrow B</math>
| [[Datei:Schulze method example1 DC.svg|ohne|150px|D-(28)-C]]
<math>D\overset{\underline{28}}\longrightarrow C</math>
|class="hintergrundfarbe5"|
| [[Datei:Schulze method example1 DE.svg|ohne|150px|D-(28)-C-(24)-E]]
<math>D\overset{28}\longrightarrow C\overset{\underline{24}}\longrightarrow E</math>
|-
|class="hintergrundfarbe5"| von <math>E</math> …
| [[Datei:Schulze method example1 EA.svg|ohne|150px|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>
| [[Datei:Schulze method example1 EB.svg|ohne|150px|E-(31)-D-(28)-C-(29)-B]]
<math>E\overset{31}\longrightarrow D\overset{\underline{28}}\longrightarrow C\overset{29}\longrightarrow B</math>
| [[Datei:Schulze method example1 EC.svg|ohne|150px|E-(31)-D-(28)-C]]
<math>E\overset{31}\longrightarrow D\overset{\underline{28}}\longrightarrow C</math>
| [[Datei:Schulze method example1 ED.svg|ohne|150px|E-(31)-D]]
<math>E\overset{\underline{31}}\longrightarrow D</math>
|class="hintergrundfarbe5"|
|}

==== 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.
{| class="wikitable hintergrundfarbe-basis" style="border: 0; text-align: center;"
|-
|style="border-top:0;border-left:0;"|
|class="hintergrundfarbe5"| <math>p[\ast,A]</math>
|class="hintergrundfarbe5"| <math>p[\ast,B]</math>
|class="hintergrundfarbe5"| <math>p[\ast,C]</math>
|class="hintergrundfarbe5"| <math>p[\ast,D]</math>
|class="hintergrundfarbe5"| <math>p[\ast,E]</math>
|-
|class="hintergrundfarbe5"| <math>p[A,\ast]</math>
|class="hintergrundfarbe5"| ||style="background:#FEDBCA; color:#202122;"| 28 ||style="background:#FEDBCA; color:#202122;"| 28 ||style="background:#FEDBCA; color:#202122;"|30 || 24
|-
|class="hintergrundfarbe5"| <math>p[B,\ast]</math>
| 25 ||class="hintergrundfarbe5"| || 28 ||style="background:#FEDBCA; color:#202122;"|33 || 24
|-
|class="hintergrundfarbe5"| <math>p[C,\ast]</math>
| 25 ||style="background:#FEDBCA; color:#202122;"| 29 ||class="hintergrundfarbe5"| ||style="background:#FEDBCA; color:#202122;"| 29 || 24
|-
|class="hintergrundfarbe5"| <math>p[D,\ast]</math>
| 25 || 28 || 28 ||class="hintergrundfarbe5"| || 24
|-
|class="hintergrundfarbe5"| <math>p[E,\ast]</math>
|style="background:#FEDBCA; color:#202122;"| 25 ||style="background:#FEDBCA; color:#202122;"| 28 ||style="background:#FEDBCA; color:#202122;"| 28 ||style="background:#FEDBCA; color:#202122;"|31 ||class="hintergrundfarbe5"|
|}

==== 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 ===

{| class="wikitable hintergrundfarbe-basis" style="border: 0; text-align: center;"
|-
! 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>
|-
|style="border-bottom:0;border-left:0;"|
! style="width:30px"| <math>3</math>
! style="width:30px"| <math>2</math>
! style="width:30px"| <math>2</math>
! style="width:30px"| <math>2</math>
|}

==== Paarweise Matrix ====

{| class="wikitable hintergrundfarbe-basis" style="border: 0; text-align: center;"
|-
|style="border-top:0;border-left:0;"|
|class="hintergrundfarbe5"| <math>d[\ast,A]</math>
|class="hintergrundfarbe5"| <math>d[\ast,B]</math>
|class="hintergrundfarbe5"| <math>d[\ast,C]</math>
|class="hintergrundfarbe5"| <math>d[\ast,D]</math>
|-
|class="hintergrundfarbe5"| <math>d[A,\ast]</math>
|class="hintergrundfarbe5"| ||style="background:#FEDBCA; color:#202122;"| 5 ||style="background:#FEDBCA; color:#202122;"| 5 || 3
|-
|class="hintergrundfarbe5"| <math>d[B,\ast]</math>
| 4 ||class="hintergrundfarbe5"| ||style="background:#FEDBCA; color:#202122;"| 7 ||style="background:#FEDBCA; color:#202122;"| 5
|-
|class="hintergrundfarbe5"| <math>d[C,\ast]</math>
| 4 || 2 ||class="hintergrundfarbe5"| ||style="background:#FEDBCA; color:#202122;"| 5
|-
|class="hintergrundfarbe5"| <math>d[D,\ast]</math>
|style="background:#FEDBCA; color:#202122;"| 6 || 4 || 4 ||class="hintergrundfarbe5"|
|}

==== Paarweiser Graph ====

[[Datei:Schulze method example4.svg|rahmenlos|klasse=skin-invert|ohne|210px]]

==== Die stärksten Wege ====

Die kritischen Siege der stärksten Wege sind unterstrichen.

{| class="wikitable hintergrundfarbe-basis skin-invert-image" style="border: 0; text-align: center;"
|-
|style="border-top:0;border-left:0;"|
|class="hintergrundfarbe5"| … nach <math>A</math>
|class="hintergrundfarbe5"| … nach <math>B</math>
|class="hintergrundfarbe5"| … nach <math>C</math>
|class="hintergrundfarbe5"| … nach <math>D</math>
|-
|class="hintergrundfarbe5"| von <math>A</math> …
|class="hintergrundfarbe5"|
| [[Datei:Schulze method example4 AB.svg|ohne|120px]]
<math>A\overset{\underline{5}}\longrightarrow B</math>
| [[Datei:Schulze method example4 AC.svg|ohne|120px]]
<math>A\overset{\underline{5}}\longrightarrow C</math>
| [[Datei:Schulze method example4 AD.svg|ohne|120px]]
<math>A\overset{\underline{5}}\longrightarrow B\overset{\underline{5}}\longrightarrow D</math>
|-
|class="hintergrundfarbe5"| von <math>B</math> …
| [[Datei:Schulze method example4 BA.svg|ohne|120px]]
<math>B\overset{\underline{5}}\longrightarrow D\overset{6}\longrightarrow A</math>
|class="hintergrundfarbe5"|
| [[Datei:Schulze method example4 BC.svg|ohne|120px]]
<math>B\overset{\underline{7}}\longrightarrow C</math>
| [[Datei:Schulze method example4 BD.svg|ohne|120px]]
<math>B\overset{\underline{5}}\longrightarrow D</math>
|-
|class="hintergrundfarbe5"| von <math>C</math> …
| [[Datei:Schulze method example4 CA.svg|ohne|120px]]
<math>C\overset{\underline{5}}\longrightarrow D\overset{6}\longrightarrow A</math>
| [[Datei:Schulze method example4 CB.svg|ohne|120px]]
<math>C\overset{\underline{5}}\longrightarrow D\overset{6}\longrightarrow A\overset{\underline{5}}\longrightarrow B</math>
|class="hintergrundfarbe5"|
| [[Datei:Schulze method example4 CD.svg|ohne|120px]]
<math>C\overset{\underline{5}}\longrightarrow D</math>
|-
|class="hintergrundfarbe5"| von <math>D</math> …
| [[Datei:Schulze method example4 DA.svg|ohne|120px]]
<math>D\overset{\underline{6}}\longrightarrow A</math>
| [[Datei:Schulze method example4 DB.svg|ohne|120px]]
<math>D\overset{6}\longrightarrow A\overset{\underline{5}}\longrightarrow B</math>
| [[Datei:Schulze method example4 DC.svg|ohne|120px]]
<math>D\overset{6}\longrightarrow A\overset{\underline{5}}\longrightarrow C</math>
|class="hintergrundfarbe5"|
|}

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

{| class="wikitable hintergrundfarbe-basis" style="border: 0; text-align: center;"
|-
|style="border-top:0;border-left:0;"|
|class="hintergrundfarbe5"| <math>p[\ast,A]</math>
|class="hintergrundfarbe5"| <math>p[\ast,B]</math>
|class="hintergrundfarbe5"| <math>p[\ast,C]</math>
|class="hintergrundfarbe5"| <math>p[\ast,D]</math>
|-
|class="hintergrundfarbe5"| <math>p[A,\ast]</math>
|class="hintergrundfarbe5"| ||style="background:#DBCAFE; color:#202122;"| 5 ||style="background:#DBCAFE; color:#202122;"| 5 || 5
|-
|class="hintergrundfarbe5"| <math>p[B,\ast]</math>
|style="background:#DBCAFE; color:#202122;"| 5 ||class="hintergrundfarbe5"| ||style="background:#FEDBCA; color:#202122;"| 7 ||style="background:#DBCAFE; color:#202122;"| 5
|-
|class="hintergrundfarbe5"| <math>p[C,\ast]</math>
|style="background:#DBCAFE; color:#202122;"| 5 || 5 ||class="hintergrundfarbe5"| ||style="background:#DBCAFE; color:#202122;"| 5
|-
|class="hintergrundfarbe5"| <math>p[D,\ast]</math>
|style="background:#FEDBCA; color:#202122;"| 6 ||style="background:#DBCAFE; color:#202122;"| 5 ||style="background:#DBCAFE; color:#202122;"| 5 ||class="hintergrundfarbe5"|
|}

==== 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 <code>C</code> die Anzahl der Kandidaten. Dann lassen sich die Stärken der stärksten Wege mit Hilfe des [[Algorithmus von Floyd und Warshall]] berechnen.

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

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

=== 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 [[Heuristik]]en 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: [http://m-schulze.9mail.de/schulze1.pdf ''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: [http://www.votingmatters.org.uk/ISSUE3/P5.HTM ''Properties of Preferential Election Rules''.] Dezember 1994 (englisch)</ref> (Zur Erläuterung der wichtigsten Kriterien siehe [[Sozialwahltheorie#Qualitätskriterien|Abschnitt Qualitätskriterien]] im Artikel ''Sozialwahltheorie''):
# Majority criterion
# Mutual majority criterion
# Monotonicity criterion (auch bezeichnet als non-negative responsiveness, mono-raise)
# Pareto criterion
# [[Condorcet-Methode#Condorcet-Kriterium|Condorcet-Kriterium]]
# [[Condorcet-Methode#Condorcet-Verliererkriterium|Condorcet-Verlierer-Kriterium]]
# Smith criterion (auch bezeichnet als Generalized Condorcet criterion)
# Local independence from irrelevant alternatives
# [[Schwartz-Menge|Schwartz-Kriterium]]
# Strategy-Free criterion
# Generalized Strategy-Free criterion
# Strong Defensive Strategy criterion
# Weak Defensive Strategy criterion
# Summability criterion
# Independence of clones
# [[Arrow-Theorem|nicht-diktatorisch]]
# [[Arrow-Theorem|Universalität]]
# Woodall’s plurality criterion
# Woodall’s CDTT criterion
# Minimal Defense criterion
# Resolvability
# Reversal symmetry
# mono-append
# mono-add-plump

Die Schulze-Methode verletzt

# das [[Majority Judgment#Konsistenzkriterium|Konsistenzkriterium]],
# das Partizipationskriterium,
# die Unabhängigkeit von irrelevanten Alternativen
# sowie das Favorite-betrayal-Kriterium.

== Anwendungen ==

[[Datei:Voting2.png|mini|klasse=skin-invert-image|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:

* [[Wikimedia|Wikimedia Foundation]]<ref>[https://lists.wikimedia.org/pipermail/foundation-l/2008-May/043134.html Board election to use preference voting, Mai 2008]</ref>
* [[Piratenpartei Deutschland]]<ref>{{Webarchiv |url=http://bremen.piratenpartei.de/Blog/2010-8-13/piraten-starten-grossversuch-zu-direkter-demokratie/ |text=Presseerklärung der Piratenpartei Deutschland |wayback=20110529194940 |archiv-bot=2019-05-12 22:14:03 InternetArchiveBot}}, August 2010</ref>
* [[Piratpartiet|Piratenpartei Schweden]]<ref>[http://viktualiebrodern.wordpress.com/2010/01/26/probewahl-der-schwedischen-piraten-ergebnis/ Probewahl der schwedischen Piraten], Januar 2010</ref>
* [[Piratenpartei Österreichs]]<ref>[https://wiki.piratenpartei.at/wiki/BGV2013-01/Protokoll/Wahlergebnisse wiki.piratenpartei.at]</ref>
* [[Debian]]<ref>[http://www.debian.org/devel/constitution Verfassung für das Debian-Projekt, Anhang A6]</ref>
* [[Ubuntu (Betriebssystem)|Ubuntu]]<ref>[https://lists.ubuntu.com/archives/ubuntu-irc/2012-May/001538.html Ubuntu IRC Council Position], Mai 2012</ref>
* [[Software in the Public Interest]]<ref>[http://www.spi-inc.org/corporate/resolutions/2003/2003-01-06.wta.1/ Process for adding new board members, Januar 2003]</ref>
* [[Gentoo Linux|Gentoo Foundation]]
* [[Sender Policy Framework]]<ref>{{Webarchiv |url=http://www.openspf.org/Council_Election |text=Council Election Procedures |wayback=20110716065154}}</ref>
* [[Free Software Foundation Europe|Free Software Foundation Europe (FSFE)]]<ref>§ 6 Absatz 3 der [https://web.archive.org/web/20170926105819/http://fsfe.org/about/legal/Constitution.de.pdf Satzung] (PDF; 112 kB)</ref>
* [[K Desktop Environment|KDE]]<ref>Artikel 3.4.1 der [http://ev.kde.org/rules/online_voting.php Rules of Procedures for Online Voting]</ref>
* Kingman Hall<ref>[http://zestyping.livejournal.com/111588.html Kingman adopts Condorcet voting, April 2005]</ref>
* TopCoder
* [[GNU Privacy Guard]]<ref>{{Webarchiv |url=http://logo-contest.gnupg.org/results.html |text=GnuPG Logo Vote, November 2006 |wayback=20061216125859 |archiv-bot=2019-05-12 22:14:03 InternetArchiveBot}}</ref>
* Golden Geek Award<ref>[http://boardgamegeek.com/thread/851248/2012-golden-geek-awards-nominations-open-for-boa Golden Geek Awards]</ref>
* Studierendenrat der [[Albert-Ludwigs-Universität Freiburg]]<ref>{{Internetquelle |autor= |url=https://web.archive.org/web/20250608044834/https:/www.stura.uni-freiburg.de/gremien/studierendenrat/go/at_download/file/Stura-GO_Stand_06_06_2019.pdf |titel=Geschäftsordnung des Studierendenrats der Albert-Ludwigs-Universität Freiburg |werk=stura.uni-freiburg.de |hrsg= |datum=2019-06-06 |format=PDF FDP; 55 kB |offline= |abruf=2025-05-22}}</ref>
* [[Berufsverband der Kinder- und Jugendärzte]]<ref>[http://www.bvkj.de/der-bvkj/satzung/ Satzung des BVKJ]</ref>
* [[Deutsche SchülerAkademie#Alumniorganisation|Club der Ehemaligen der Deutschen SchülerAkademien e. V.]]<ref>[https://db.cde-ev.de/doc/Realm_Assembly_Voting-Details.html#id2 Voting Details]</ref>

== Siehe auch ==

* [[Ranked Pairs]]
* [[Sozialwahltheorie]]
* [[Condorcet-Paradoxon]]
* [[LiquidFeedback]]

== Literatur ==
* Christoph Börgers: [http://books.google.de/books?id=dccBaphP1G4C&pg=PA37 ''Mathematics of Social Choice: Voting, Compensation, and Division''.] SIAM 2009, ISBN 0-89871-695-0.
* Saul Stahl, Paul E. Johnson: [http://books.google.de/books?id=CMLL9sVGLb8C&pg=PA119 ''Understanding Modern Mathematics''.] Jones & Bartlett Publishing, London u. a. 2007, ISBN 0-7637-3401-2, S. 119 ff.
* [[Nicolaus Tideman]]: [http://books.google.de/books?id=RN5q_LuByUoC&pg=PA228 ''Collective Decisions and Voting: The Potential for Public Choice''.] Ashgate Publishing, 2006, ISBN 0-7546-4717-X, S. 228 ff.

== Weblinks ==
{{Commons|Schulze method}}
* Rosa Camps, Xavier Mora, Laia Saumell: [http://mat.uab.cat/~xmora/articles/crating.pdf ''A Continuous Rating Method for Preferential Voting''.] (PDF; 1,76 MB)
* Paul E. Johnson: [https://web.archive.org/web/20250510175510/https:/pj.freefaculty.org/Ukraine/PJ3_VotingSystemsEssay.pdf ''Voting Systems''.] (PDF; 324 kB)
* Rob LeGrand: [https://rob-legrand.github.io/ranked-ballot-voting-calculator/old/desc.html ''Descriptions of ranked-ballot voting methods''.]
* Rob Loring: [http://accuratedemocracy.com/voting_rules.htm ''Accurate Democracy''.]
* James D. McCaffrey: [http://msdn.microsoft.com/de-de/magazine/dd148646.aspx ''Testlauf: Gruppenentscheidungen bei Softwaretests''.] MSDN
* Tommi Meskanen, Hannu Nurmi: [https://www.researchgate.net/profile/Hannu_Nurmi/publication/31597053_Distance_from_Consensus_A_Theme_and_Variations/links/09e415085728bc86ba000000/Distance-from-Consensus-A-Theme-and-Variations.pdf ''Distance from Consensus: a Theme and Variations''.] (PDF; 170 kB) In: Bruno Simeone, Friedrich Pukelsheim (Hrsg.): ''Mathematics and democracy'': recent advances in voting systems and collective choice. Studies in choice and welfare. Springer, Berlin u. a. 2006, ISBN 3-540-35603-7, S. 117–132, hier S. 120 ff.
* Massimo Narizzano, Luca Pulina, Armando Tacchella: [https://www.researchgate.net/publication/221153297_Ranking_and_Reputation_Systems_in_the_QBF_Competition ''Ranking and Reputation Systems in the QBF Competition''.] (PDF; 455 kB) In: ''AI*IA ’07 Proceedings of the 10th Congress of the Italian Association for Artificial Intelligence'' on AI*IA 2007: Artificial Intelligence and Human-Oriented Computing. Springer, Berlin / Heidelberg 2007, ISBN 978-3-540-74781-9.
* Markus Schulze: [https://arxiv.org/pdf/1804.02973.pdf Schulze-Methode FAQ]
* Markus Schulze: [http://www.votingmatters.org.uk/ISSUE17/I17P3.PDF ''A New Monotonic and Clone-Independent Single-Winner Election Method''.] (PDF; 74 kB) In: ''Voting Matters'', 17, 2003, S. 9–19.
* Kevin Venzke: [http://nodesiege.tripod.com/elections/ ''Election Methods and Criteria''.]
* Jochen Voss: [https://www.seehuhn.de/pages/vote.html ''The Debian Voting System''.]
* Barry Wright: [https://services.math.duke.edu/~bray/Courses/49s/Senior%20Theses/Barry%20Wright/Barry%20Wright%27s%20Thesis.pdf ''Objective Measures of Preferential Ballot Voting Systems''.] (PDF; 289 kB) Abschlussarbeit Duke University, Durham NC 2009.

== Einzelnachweise ==
<references />

[[Kategorie:Wahlverfahren]]

Schulze-Methode - Versionsgeschichte

imported>Polluks: /* Beispiel einer Implementierung in Pascal */ Pascal-like