Zum Inhalt springen

Schulze-Methode

aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 31. Juli 2007 um 11:38 Uhr durch Gerold Broser (Diskussion | Beiträge) (→Literatur: QA+). Sie kann sich erheblich von der aktuellen Version unterscheiden.

Die Schulze-Methode (nach Markus Schulze) ist ein Wahlsystem und 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. Der Wähler darf dieselbe Präferenz an mehrere Kandidaten vergeben. Er darf auch Kandidaten auslassen. Wenn ein Wähler Kandidaten auslässt, 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 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:
  1. C(1) ist identisch mit X.
  2. C(n) ist identisch mit Y.
  3. Für i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
  4. Für i = 1,...,(n-1): d[C(i),C(i+1)] ≥ z.
Gibt es ein p, so dass 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 dass der Kandidat E den Kandidaten D disqualifiziert.

Es lässt sich zeigen, dass 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:

  1. C(1) ist identisch mit X.
  2. C(n) ist identisch mit Y.
  3. 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 }.

p[A,B] : = 0, falls es keinen Weg vom Kandidaten A zum Kandidaten B gibt.

Mit anderen Worten: p[A,B] ist die Stärke des stärksten Weges vom Kandidaten A zum Kandidaten B.

Dann lässt 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.

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: Kandidat i ist ein potentieller Sieger, genau dann wenn "winner[i] = true" ist. 

 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

Beispiel 1

Beispiel (45 Wähler; 5 Kandidaten):

(Notation: #Anzahl der Personen, die folgende Reihenfolge der Kandidaten gewählt haben: Kandidat mit höchster Bevorzugung ... Kandidat mit niedrigster Bevorzugung)

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 paarweise Matrix sieht folgendermaßen aus:

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
Die stärksten Wege sind:
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
Die Stärken der stärksten Wege sind:

Sieger nach der Schulze-Methode ist Kandidat E, da p[E,X] ≥ p[X,E] ist für jeden anderen Kandidaten X.

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 paarweise Matrix sieht folgendermaßen aus:

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
Die stärksten Wege sind:
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
Die Stärken der stärksten Wege sind:

Sieger nach der Schulze-Methode ist Kandidat D, da p[D,X] ≥ p[X,D] ist für jeden anderen Kandidaten X.

Beispiel 3

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 paarweise Matrix sieht folgendermaßen aus:

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
Die stärksten Wege sind:
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
Die Stärken der stärksten Wege sind:

Sieger nach der Schulze-Methode ist Kandidat B, da p[B,X] ≥ p[X,B] ist für jeden anderen Kandidaten X.

Beispiel 4

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 paarweise Matrix sieht folgendermaßen aus:

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
Die stärksten Wege sind:
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
Die Stärken der stärksten Wege sind:

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

Dieser Artikel oder Abschnitt bedarf einer grundsätzlichen Überarbeitung. Näheres sollte auf der Diskussionsseite angegeben sein. Bitte hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Die Schulze-Methode erfüllt die folgenden Kriterien[1][2]:

  1. Majority criterion
  2. Mutual majority criterion
  3. Monotonicity criterion (a.k.a. non-negative responsiveness, mono-raise)
  4. Pareto criterion
  5. Condorcet-Kriterium
  6. Condorcet-Verlierer-Kriterium
  7. Smith criterion (a.k.a. Generalized Condorcet criterion)
  8. Local independence from irrelevant alternatives
  9. Schwartz criterion
  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

Anwendungen

Dieser Artikel oder Abschnitt bedarf einer grundsätzlichen Überarbeitung. Näheres sollte auf der Diskussionsseite angegeben sein. Bitte hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

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:

Siehe auch

Ranked Pairs, Sozialwahltheorie, Condorcet-Methode, Condorcet-Paradoxon, Marquis de Condorcet

Literatur

  1. Nicolaus Tideman: Collective Decisions and Voting: The Potential for Public Choice, Ashgate Publishing 2006, ISBN 075464717X
  2. Saul Stahl und Paul E. Johnson: Understanding Modern Mathematics, Jones & Bartlett Publishing 2006, ISBN 0763734012

Quellen

  1. ↑ A New Monotonic, Clone-Independent, Reversal Symmetric, and Condorcet-Consistent Single-Winner Election Method, Markus Schulze, Juli 2007 (PDF, englisch)
  2. ↑ Properties of Preferential Election Rules, D. R. Woodall, Dezember 1994 (englisch)

Originalliteratur

  1. A New Monotonic and Clone-Independent Single-Winner Election Method von Markus Schulze
  2. A New Monotonic, Clone-Independent, Reversal Symmetric, and Condorcet-Consistent Single-Winner Election Method von Markus Schulze
  3. Free Riding and Vote Management under Proportional Representation by the Single Transferable Vote von Markus Schulze
  4. Implementing the Schulze STV Method von Markus Schulze

Weiterführende Literatur

  1. Descriptions of ranked-ballot voting methods von Rob LeGrand
  2. Election Methods Resource von Blake Cretney
  3. Election Methods and Criteria von Kevin Venzke
  4. Election Systems von Peter A. Taylor
  5. Voting Systems von Paul E. Johnson
  6. The Maximize Affirmed Majorities voting procedure (MAM) von Steve Eppley
  7. The Debian Voting System von Jochen Voss
  8. A Survey of Basic Voting Methods von James Green-Armytage
  9. Accurate Democracy von Rob Loring
  10. Social Choice Under Incomplete, Cyclic Preferences von Jobst Heitzig (die Methode wird hier "strong immunity from binary arguments" genannt)
  11. Distance from Consensus: a Theme and Variations von Tommi Meskanen und Hannu Nurmi
  12. Analyzing Political Disagreement von Tommi Meskanen und Hannu Nurmi
  13. Descriptions of voting systems von Warren D. Smith

Software

  1. Condorcet Internet Voting Service (CIVS) von Andrew Myers
  2. Condorcet Voting Calculator von Eric Gorr
  3. BetterPolls.com von Brian Olson
  4. A different way to vote von Anguo Ma
  5. Voting Software Project von Blake Cretney
  6. Condorcet with Dual Dropping Perl Scripts von Mathew Goldstein
  7. Haskell Condorcet Module von Evan Martin
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Schulze-Methode&oldid=35014032“