Schulze-Methode

aus Wikipedia, der freien Enzyklopädie

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

Inhaltsverzeichnis 1 Definition 1.1 Anzahl der Wähler 1.2 Der Condorcet-Sieger 1.3 Formulierung 2 Beispiele 2.1 Beispiel 1 2.2 Beispiel 2 2.3 Beispiel 3 2.4 Beispiel 4 3 Eigenschaften 4 Anwendungen 5 Siehe auch 6 Literatur 7 Weblinks 7.1 Originalliteratur 7.2 Weiterführende Literatur 7.3 Software

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] Eigenschaften

Die Schulze-Methode erfüllt die folgenden Kriterien:

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

Die meisten Kriterien werden hier und hier erläutert.

[Bearbeiten] 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:

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

[Bearbeiten] Siehe auch

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

[Bearbeiten] Literatur

• Nicolaus Tideman: Collective Decisions and Voting: The Potential for Public Choice, Ashgate Publishing 2006, ISBN 075464717X

[Bearbeiten] Weblinks

[Bearbeiten] 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

[Bearbeiten] 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

[Bearbeiten] 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