Schulze-Methode

Eine gesichtete Version dieser Seite, die am 22. Juni 2009 freigegeben wurde, basiert auf dieser Version.

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

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

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:

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: p[i,j] ist die Stärke des stärksten Weges vom Kandidaten i zum Kandidaten j.

for i : = 1 to C
begin
   for j : = 1 to C
   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
begin
   for j : = 1 to C
   begin
      if ( i ≠ j ) then
      begin
         for k : = 1 to C
         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

Eigenschaften

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

Majority criterion
Mutual majority criterion
Monotonicity criterion (auch bezeichnet als non-negative responsiveness, mono-raise)
Pareto criterion
Condorcet-Kriterium
Condorcet-Verlierer-Kriterium
Smith criterion (auch bezeichnet als 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

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

Weblinks

Schulze-Methode FAQ von Markus Schulze
A New Monotonic and Clone-Independent Single-Winner Election Method von Markus Schulze (PDF-Datei; 602 kB)
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 (PDF-Datei; 324 kB)
Testlauf: Gruppenentscheidungen bei Softwaretests von James D. McCaffrey
A Continuous Rating Method for Preferential Voting von Rosa Camps, Xavier Mora und Laia Saumell (PDF-Datei; 1,76 MB)
Distance from Consensus: a Theme and Variations von Tommi Meskanen und Hannu Nurmi (PDF-Datei; 130 kB)
Analyzing Political Disagreement von Tommi Meskanen und Hannu Nurmi (PDF-Datei; 603 kB)

[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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]