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

Η **μέθοδος Σούλτσε** είναι σύστημα ψηφοφορίας που αναπτύχθηκε το 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)] &gt; 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] &gt; 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

border|none|300px

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

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

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

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

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

### Διαδικασία

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

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

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

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

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

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