Μέθοδος Σούλτσε
 |
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Η μέθοδος Σούλτσε είναι σύστημα ψηφοφορίας που αναπτύχθηκε το 1997 από τον Μάρκους Σούλτσε και που επιλέγει έναν μοναδικό νικητή με τη χρήση ψήφων που εκφράζουν προτιμήσεις. Η μέθοδος μπορεί να χρησιμοποιηθεί επίσης για τη δημιουργία μιας ταξινομημένης λίστας από νικητές.
Αν υπάρχει υποψήφιος που προτιμάται κατά ζεύγος από τους άλλους υποψηφίους, όταν συγκριθεί με κάθε άλλον διαδοχικά, η μέθοδος Σούλτσε εξασφαλίζει ότι θα νικήσει αυτός. Εξαιτίας της ιδιότητας αυτής, η μέθοδος Σούλτσε είναι εξ ορισμού μια μέθοδος Κοντορσέ.
Σήμερα η μέθοδος Σούλτσε είναι η πιο ευρέως χρησιμοποιημένη μέθοδος Κοντορσέ. Η μέθοδος Σούλτσε χρησιμοποιείται μεταξύ άλλων από το ίδρυμα Wikimedia, την κοινότητα του Gentoo και του Debian Linux, και τη μη κερδοσκοπική οργάνωση Software in the Public Interest.
Πολλές διαφορετικές ευρετικές μέθοδοι για τη μέθοδο Σούλτσε έχουν προταθεί. Οι πιο σημαντικές ευρετικές είναι η ευρετική του μονοπατιού και η ευρετική συνόλου Σβαρτς που περιγράφονται παρακάτω. Όλες οι ευρετικές μέθοδοι βρίσκουν τον ίδιο νικητή και διαφέρουν μόνο στις λεπτομέρειες της υπολογιστικής διαδικασίας για το καθορισμό αυτού του νικητή.
Η ευρετική μέθοδος μονοπατιού
[Επεξεργασία | επεξεργασία κώδικα]
Κατά τη μέθοδο Σούλτσε (καθώς και κατά άλλες μεθόδους ψηφοφορίας κατά προτίμηση με μοναδικό νικητή), κάθε ψηφοδέλτιο περιέχει έναν πλήρη κατάλογο όλων των υποψηφίων, και ο ψηφοφόρος βαθμολογεί τα μέλη του καταλόγου ανάλογα με τις προτιμήσεις του. Σύμφωνα με μια συχνή διάταξη ψηφοδελτίου (όπως στην εικόνα δεξιά), χρησιμοποιούνται αριθμοί σε αύξουσα σειρά, και ο χρήστης βάζει '1' δίπλα στον προτιμότερο υποψήφιο, '2' δίπλα στον δεύτερο πιο προτιμότερο, κ.ο.κ. Οι ψηφοφόροι μπορούν να δώσουν την ίδια προτίμηση σε περισσότερους από έναν υποψηφίους και επιτρέπεται επίσης να μη βαθμολογήσουν μερικούς υποψήφιους. Όταν ένας ψηφοφόρος δεν βαθμολογεί όλους τους υποψηφίους, υποτίθεται ότι αυτός ο ψηφοφόρος αυστηρά προτιμά όλους τους βαθμολογημένους υποψηφίους παρά όλους τους μη βαθμολογημένους και ότι αυτός ο ψηφοφόρος αδιαφορεί ως προς την ταξινόμηση όλων των μη βαθμολογημένων υποψηφίων.
Διαδικασία
[Επεξεργασία | επεξεργασία κώδικα]Έστω d[V,W] ο αριθμός ψηφοφόρων που αυστηρά προτιμούν τον υποψήφιο V παρά τον υποψήφιο W.
Ένα μονοπάτι (path) από τον υποψήφιο X στον υποψήφιο Y με δύναμη (strength) p είναι μια σειρά από υποψηφίους C(1),...,C(n) με τις εξής ιδιότητες:
- C(1) = X και C(n) = Y.
- Για κάθε i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
- Η 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 ο αριθμός υποψηφίων. Τότε οι δυνάμεις των πιο δυνατών μονοπατιών υπολογίζονται με τον αλγόριθμο Φλόιντ-Γουάρσαλ.
Είσοδος: το 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 ... |  |
 |
 |
 | |
| από τον B ... |  |
 |
 |
 | |
| από τον C ... |  |
 |
 |
 | |
| από τον D ... |  |
 |
 |
 | |
| από τον E ... |  |
 |
 |
 |
| 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.
Η ευρετική μέθοδος με σύνολο Σβαρτς
[Επεξεργασία | επεξεργασία κώδικα]Το σύνολο Σβαρτς
[Επεξεργασία | επεξεργασία κώδικα]Το σύνολο Σβαρτς, όπως χρησιμοποιείται στη μέθοδο Σούλτσε, ορίζεται ως εξής:
- Ένα ανίκητο σύνολο είναι ένα σύνολο υποψηφίων από τους οποίους κανένας δεν νικήθηκε από κάποιον από έξω από εκείνο το σύνολο.
- Ένα εσώτερο ανίκητο σύνολο είναι ένα ανίκητο σύνολο που δεν περιέχει ένα μικρότερο ανίκητο σύνολο.
- Το σύνολο Σβαρτς είναι το σύνολο υποψηφίων που βρίσκονται στα εσώτερα ανίκητα σύνολα.
Διαδικασία
[Επεξεργασία | επεξεργασία κώδικα]Οι ψηφοφόροι ρίχνουν την ψήφο τους βαθμολογώντας τους υποψηφίους ανάλογα με τις προτιμήσεις τους, όπως σε κάθε άλλη εκλογή Κοντορσέ.
Η μέθοδος Σούλτσε χρησιμοποιεί κατά ζεύγη σύγκριση μεταξύ των υποψηφίων και ένας νικητής επιλέγεται από κάθε ζεύγος.
Από εκείνο το σημείο, η μέθοδος Σούλτσε λειτουργεί ως εξής ώστε να επιλέξει έναν νικητή (ή για να δημιουργήσει μια ταξινομημένη λίστα):
- Υπολογίζουμε το σύνολο Σβαρτς με βάση μόνο τις ήττες που δεν έχουν απορριφθεί.
- Αν δεν υπάρχουν ήττες ανάμεσα στα μέλη εκείνου του συνόλου, τότε αυτά τα μέλη (ή το μοναδικό μέλος, αν παραμένει μόνο ένα μέλος) νικούν και η μέτρηση τελειώνει.
- Αλλιώς, απορρίπτουμε την πιο αδύναμη (με τη πιο μικρή διαφορά πόντων) ήττα (ή ήττες, στην περίπτωση που περισσότερες από μία είναι εξίσου αδύναμες), ανάμεσα στους υποψηφίους που ανήκουν σε εκείνο το σύνολο. Επιστρέφουμε στο βήμα 1.
