Μέθοδος Σούλτσε

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

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

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

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

 Η ευρετική μέθοδος μονοπατιού 
150px|right|thumb|Δείγμα ενός ψηφοδελτίου με μέθοδο Σούλτσε

Κατά τη μέθοδο Σούλτσε (καθώς και κατά άλλες μεθόδους ψηφοφορίας κατά προτίμηση με μοναδικό νικητή), κάθε ψηφοδέλτιο περιέχει έναν πλήρη κατάλογο όλων των υποψηφίων, και ο ψηφοφόρος βαθμολογεί τα μέλη του καταλόγου ανάλογα με τις προτιμήσεις του. Σύμφωνα με μια συχνή διάταξη ψηφοδελτίου (όπως στην εικόνα δεξιά), χρησιμοποιούνται αριθμοί σε αύξουσα σειρά, και ο χρήστης βάζει '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 ...   border|none|150px A-(30)-D-(28)-C-(29)-B  border|none|150px A-(30)-D-(28)-C  border|none|150px A-(30)-D  border|none|150px A-(30)-D-(28)-C-(24)-E από τον B ...  border|none|150px B-(25)-A   border|none|150px B-(33)-D-(28)-C  border|none|150px B-(33)-D  border|none|150px B-(33)-D-(28)-C-(24)-E από τον C ...  border|none|150px C-(29)-B-(25)-A  border|none|150px C-(29)-B   border|none|150px C-(29)-B-(33)-D  border|none|150px C-(24)-E από τον D ...  border|none|150px D-(28)-C-(29)-B-(25)-A  border|none|150px D-(28)-C-(29)-B  border|none|150px D-(28)-C   border|none|150px D-(28)-C-(24)-E από τον E ...  border|none|150px E-(31)-D-(28)-C-(29)-B-(25)-A  border|none|150px E-(31)-D-(28)-C-(29)-B  border|none|150px E-(31)-D-(28)-C  border|none|150px 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.

 Η ευρετική μέθοδος με σύνολο Σβαρτς 
 Το σύνολο Σβαρτς 

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

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

 Διαδικασία 

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

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

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

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

 Εξωτερικοί σύνδεσμοι 

Κατηγορία:Εκλογικά συστήματα
Κατηγορία:Debian