Schulze-Methode

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

all diejenigen Kandidaten, an die er eine Präferenz vergeben hat, all denjenigen Kandidaten, die er ausgelassen hat, strikt vorzieht und
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:

C(1) ist identisch mit X.
C(n) ist identisch mit Y.
Für i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
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:

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

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

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

5 ACBD

2 ACDB

3 ADCB

4 BACD

3 CBDA

3 CDBA

1 DACB

5 DBAC

4 DCBA

Die paarweise Matrix sieht folgendermaßen aus:
	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 kritischen Siege der stärksten Wege sind unterstrichen.

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

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

Die paarweise Matrix sieht folgendermaßen aus:
	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 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-(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ärken der 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

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

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

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.

Eigenschaften

Die Schulze-Methode erfüllt die folgenden Kriterien:

Majority criterion
Mutual majority criterion
Monotonicity criterion (a.k.a. non-negative responsiveness, mono-raise)
Pareto criterion
Condorcet-Kriterium
Condorcet-Verlierer-Kriterium
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
nicht-diktatorisch
Universalität
Woodall's plurality criterion
Woodall's CDTT criterion
Minimal Defense criterion
Resolvability
Reversal symmetry
mono-append
mono-add-plump

Die meisten Kriterien werden hier und hier erläutert.

Anwendungen

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:

Wikipédia francophone (siehe hier)
Debian (siehe Anhang A6 der Verfassung)
Software in the Public Interest (SPI) [1]
Gentoo Foundation [2] [3] [4] [5] [6]
League of Professional System Administrators (LOPSA) (siehe Artikel 8.3 der Verfassung)
Sender Policy Framework (SPF) [7] [8]
Mathematical Knowledge Management Interest Group (MKM-IG) [9] [10] [11]
Park Alumni Society (PAS) [12]
Kingman Hall [13] [14]
Blitzed [15]
Democratic Experience (DemExp) (siehe Kapitel 40.6 dieses Papers)
TopCoder [16] [17] [18] [19] [20] [21] [22]
GNU Privacy Guard [23]
Pittsburgh Ultimate [24]

Siehe auch

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

Literatur

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