Cloneproof Schwartz Sequential Dropping

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. all den ausgelassenen Kandidaten dieselbe Präferenz zuteilt.

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 eine Sequenz 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 alle i = 1,…,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
4. Für alle i = 1,…,(n-1): d[C(i),C(i+1)] ≥ z.
5. Für mindestens ein i = 1,…,(n-1): d[C(i),C(i+1)] = z.

p[A,B], die Stärke des stärksten Weges vom Kandidaten A zum Kandidaten B, ist der größte Wert, so dass es einen Weg dieser Stärke vom Kandidaten A zum Kandidaten B gibt. p[A,B] : = 0, falls es keinen Weg vom Kandidaten A zum Kandidaten B gibt.

Kandidat D ist besser als Kandidat E, genau dann wenn p[D,E] > p[E,D] ist.

Kandidat D ist ein potentieller Sieger, genau dann wenn p[D,E] ≥ p[E,D] ist für jeden anderen Kandidaten E.

Es lässt sich zeigen, dass es stets mindestens einen potentiellen Sieger gibt.

Beispiele

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

Die paarweise Matrix sieht folgendermaßen aus:

	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

Der paarweise Graph sieht folgendermaßen aus:

Datei:Schulze method example1.png

Die kritischen Siege der stärksten Wege sind unterstrichen.

Die stärksten Wege sind:

	… 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ärken der 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

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 (9 Wähler; 4 Kandidaten):

3 ABCD

2 DABC

2 DBCA

2 CBDA

Die paarweise Matrix sieht folgendermaßen aus:

	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

Der paarweise Graph sieht folgendermaßen aus:

Datei:Schulze method example4.png

Die kritischen Siege der stärksten Wege sind unterstrichen.

Die stärksten Wege sind:

	… 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ärken der 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

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.

Implementation

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

Eigenschaften

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

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

Muster für die elektronischen Stimmzettel für die Wahlen zum Kuratorium der Wikimedia Foundation

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:

• Wikimedia ^[3]
• französischsprachige Wikipedia ^[4]
• Debian ^[5]
• Software in the Public Interest ^[6]
• Gentoo Foundation
• Sender Policy Framework ^[7]
• Free Software Foundation Europe (FSFE) ^[8]
• KDE e.V. ^[9]
• Mathematical Knowledge Management Interest Group (MKM-IG)
• Kingman Hall ^[10]
• TopCoder
• GNU Privacy Guard ^[11]

Siehe auch

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

Literatur

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

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)
3. ↑ Board election to use preference voting, Mai 2008
4. ↑ Prise de décision, Dezember 2005
5. ↑ Verfassung für das Debian-Projekt, Anhang A6
6. ↑ Process for adding new board members, Januar 2003
7. ↑ Council Election Procedures
8. ↑ § 6 Absatz 3 der Satzung
9. ↑ Artikel 3.4.1 der Rules of Procedures for Online Voting
10. ↑ Kingman adopts Condorcet voting, April 2005
11. ↑ GnuPG Logo Vote, November 2006

Weblinks

• Schulze-Methode FAQ von Markus Schulze
• A New Monotonic and Clone-Independent Single-Winner Election Method von Markus Schulze
• Election Methods Resource von Blake Cretney
• Descriptions of ranked-ballot voting methods von Rob LeGrand
• Accurate Democracy von Rob Loring
• Election Methods and Criteria von Kevin Venzke
• The Debian Voting System von Jochen Voss
• Voting Systems von Paul E. Johnson
• Testlauf: Gruppenentscheidungen bei Softwaretests von James D. McCaffrey
• A Continuous Rating Method for Preferential Voting von Rosa Camps, Xavier Mora und Laia Saumell
• Distance from Consensus: a Theme and Variations von Tommi Meskanen und Hannu Nurmi
• Analyzing Political Disagreement von Tommi Meskanen und Hannu Nurmi