Μέθοδος Schulze

Η μέθοδος Schulze είναι ένα σύστημα ψηφοφορίας που αναπτύχθηκε το 1997 από τον Markus Schulze και που επιλέγει έναν μοναδικό νικητή με τη χρήση ψήφων που εκφράζουν προτιμήσεις. Η μέθοδος μπορεί να χρησιμοποιηθεί επίσης για τη δημιουργία μιας ταξινομημένης λίστας από νικητές.

Αν υπάρχει υποψήφιος που προτιμάται κατά ζεύγος από τους άλλους υποψηφίους, όταν συγκριθεί με κάθε άλλον διαδοχικά, η μέθοδος Schulze εξασφαλίζει ότι θα νικήσει αυτός. Εξαιτίας της ιδιότητας αυτής, η μέθοδος Schulze είναι εξ ορισμού μια μέθοδος Κοντορσέ.

Σήμερα η μέθοδος Schulze είναι η πιο ευρέως χρησιμοποιημένη μέθοδος Κοντορσέ. Η μέθοδος Schulze χρησιμοποιείται μεταξύ άλλων από το ίδρυμα Wikimedia, την κοινότητα του Gentoo και του Debian Linux, και τη μη κερδοσκοπική οργάνωση Software in the Public Interest.

Πολλές διαφορετικές ευρετικές μέθοδοι για τη μέθοδο Schulze έχουν προταθεί. Οι πιο σημαντικές ευρετικές είναι η ευρετική του μονοπατιού και η ευρετική συνόλου Schwartz που περιγράφονται παρακάτω. Όλες οι ευρετικές μέθοδοι βρίσκουν τον ίδιο νικητή και διαφέρουν μόνο στις λεπτομέρειες της υπολογιστικής διαδικασίας για το καθορισμό αυτού του νικητή.

Η ευρετική μέθοδος μονοπατιού

Δείγμα ενός ψηφοδελτίου με μέθοδο Schulze

Κατά τη μέθοδο Schulze (καθώς και κατά άλλες μεθόδους ψηφοφορίας κατά προτίμηση με μοναδικό νικητή), κάθε ψηφοδέλτιο περιέχει έναν πλήρη κατάλογο όλων των υποψηφίων, και ο ψηφοφόρος βαθμολογεί τα μέλη του καταλόγου ανάλογα με τις προτιμήσεις του. Σύμφωνα με μια συχνή διάταξη ψηφοδελτίου (όπως στην εικόνα δεξιά), χρησιμοποιούνται αριθμοί σε αύξουσα σειρά, και ο χρήστης βάζει '1' δίπλα στον προτιμότερο υποψήφιο, '2' δίπλα στον δεύτερο πιο προτιμότερο, κ.ο.κ. Οι ψηφοφόροι μπορούν να δώσουν την ίδια προτίμηση σε περισσότερους από έναν υποψηφίους και επιτρέπεται επίσης να μη βαθμολογήσουν μερικούς υποψήφιους. Όταν ένας ψηφοφόρος δεν βαθμολογεί όλους τους υποψηφίους, υποτίθεται ότι αυτός ο ψηφοφόρος αυστηρά προτιμά όλους τους βαθμολογημένους υποψηφίους παρά όλους τους μη βαθμολογημένους και ότι αυτός ο ψηφοφόρος αδιαφορεί ως προς την ταξινόμηση όλων των μη βαθμολογημένων υποψηφίων.

Διαδικασία

Έστω d[V,W] ο αριθμός ψηφοφόρων που αυστηρά προτιμούν τον υποψήφιο V παρά τον υποψήφιο W.

Ένα μονοπάτι (path) από τον υποψήφιο X στον υποψήφιο Y με δύναμη (strength) p είναι μια σειρά από υποψηφίους C(1),...,C(n) με τις εξής ιδιότητες:

1. C(1) = X και C(n) = Y.
2. Για κάθε i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
3. Η p είναι η ελάχιστη τιμή όλων των d[C(i),C(i+1)] για i = 1,...,(n-1).

Η p[A,B], η δύναμη του πιο δυνατού μονοπατιού από τον υποψήφιο A στον υποψήφιο B, είναι η μεγαλύτερη τιμή ώστε να υπάρχει ένα μονοπάτι από τον υποψήφιο A στον υποψήφιο B με εκείνη τη δύναμη. Αν δεν υπάρχει κανένα μονοπάτι από τον υποψήφιο A στον υποψήφιο B, τότε p[A,B] : = 0.

Ο υποψήφιος D είναι καλύτερος από τον υποψήφιο E αν και μόνο αν p[D,E] > p[E,D].

Ο υποψήφιος D είναι πιθανός νικητής αν και μόνο αν p[D,E] ≥ p[E,D] για κάθε άλλον υποψήφιο E.

Υλοποίηση

Έστω C ο αριθμός υποψηφίων. Τότε οι δυνάμεις των πιο δυνατών μονοπατιών υπολογίζονται με τον αλγόριθμο Floyd–Warshall.

Είσοδος: το d[i,j] είναι ο αριθμός ψηφοφόρων που αυστηρά προτιμούν τον υποψήφιο i παρά τον υποψήφιο j.

Έξοδος: Ο υποψήφιος i είναι πιθανός νικητής αν και μόνο αν "winner[i] = true".

 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

Παράδειγμα 1

Παράδειγμα (45 ψηφοφόροι; 5 υποψήφιοι):

5 ACBED (Δηλαδή, 5 ψηφοφόροι έχουν σειρά προτίμησης: A > C > B > E > D)

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

Οι κρίσιμες ήττες των πιο δυνατών μονοπατιών είναι υπογεγραμμένες.

Τα πιο δυνατά μονοπάτια είναι:

	... στον A	... στον B	... στον C	... στον D	... στον E
από τον A ...		A-(30)-D-(28)-C-(29)-B	A-(30)-D-(28)-C	A-(30)-D	A-(30)-D-(28)-C-(24)-E
από τον B ...	B-(25)-A		B-(33)-D-(28)-C	B-(33)-D	B-(33)-D-(28)-C-(24)-E
από τον C ...	C-(29)-B-(25)-A	C-(29)-B		C-(29)-B-(33)-D	C-(24)-E
από τον D ...	D-(28)-C-(29)-B-(25)-A	D-(28)-C-(29)-B	D-(28)-C		D-(28)-C-(24)-E
από τον 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

Η δύναμη των πιο δυνατών μονοπατιών είναι:

	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

Ο υποψήφιος E είναι πιθανός νικητής γιατί p[E,X] ≥ p[X,E] για κάθε άλλον υποψήφιο X.

Η ευρετική μέθοδος με σύνολο Schwartz

Το σύνολο Schwartz

Το σύνολο Schwartz, όπως χρησιμοποιείται στη μέθοδο Schulze, ορίζεται ως εξής:

1. Ένα ανίκητο σύνολο είναι ένα σύνολο υποψηφίων από τους οποίους κανένας δεν νικήθηκε από κάποιον από έξω από εκείνο το σύνολο.
2. Ένα εσώτερο ανίκητο σύνολο είναι ένα ανίκητο σύνολο που δεν περιέχει ένα μικρότερο ανίκητο σύνολο.
3. Το σύνολο Schwartz είναι το σύνολο υποψηφίων που βρίσκονται στα εσώτερα ανίκητα σύνολα.

Διαδικασία

Οι ψηφοφόροι ρίχνουν την ψήφο τους βαθμολογώντας τους υποψηφίους ανάλογα με τις προτιμήσεις τους, όπως σε κάθε άλλη εκλογή Κοντορσέ.

Η μέθοδος Schulze χρησιμοποιεί κατά ζεύγη σύγκριση μεταξύ των υποψηφίων και ένας νικητής επιλέγεται από κάθε ζεύγος.

Από εκείνο το σημείο, η μέθοδος Schulze λειτουργεί ως εξής ώστε να επιλέξει έναν νικητή (ή για να δημιουργήσει μια ταξινομημένη λίστα):

1. Υπολογίζουμε το σύνολο Schwartz με βάση μόνο τις ήττες που δεν έχουν απορριφθεί.
2. Αν δεν υπάρχουν ήττες ανάμεσα στα μέλη εκείνου του συνόλου, τότε αυτά τα μέλη (ή το μοναδικό μέλος, αν παραμένει μόνο ένα μέλος) νικούν και η μέτρηση τελειώνει.
3. Αλλιώς, απορρίπτουμε την πιο αδύναμη (με τη πιο μικρή διαφορά πόντων) ήττα (ή ήττες, στην περίπτωση που περισσότερες από μία είναι εξίσου αδύναμες), ανάμεσα στους υποψηφίους που ανήκουν σε εκείνο το σύνολο. Επιστρέφουμε στο βήμα 1.