| Περίληψη: | Η ψηφοφορία είναι ένας δημοφιλής τρόπος για κατανεμημένη λήψη αποφάσεων και παραδοσιακά είναι το αντικείμενο της θεωρίας κοινωνικής επιλογής έχοντας ως κεντρικό πρόβλημα το πως θα φτάσουμε ομόφωνα σε μια κοινωνικά καλή απόφαση έχοντας ως δεδομένο τις προτιμήσεις των ψηφοφόρων πάνω σε ένα σύνολο από υποψηφίους. Πολλά συστήματα ψηφοφορίας έχουν εμφανιστεί στη σχετική βιβλιογραφία από τότε που οι Borda και Marquis de Condorcet πρότειναν στα τέλη του 18ου αιώνα τα πρώτα συστήματα. Ενώ οι περισσότερες από τις σχετικές έρευνες εστιάζουν στις ιδιότητες των συστημάτων ψηφοφορίας για κυβερνητικές εκλογές ή λήψη αποφάσεων σε επιτροπές, η εμφάνιση εφαρμογών μεγάλης κλίμακας για εξόρυξη πληροφορίας, κατάταξη, και ανάκτηση έχει βάλει την ψηφοφορία στην ημερήσια διάταξη της έρευνας της επιστήμης των υπολογιστών. Όντως, προβλήματα σαν την κατάταξη συνόλων μπορούν να θεωρηθούν ως προβλήματα εκλογών. Στα προβλήματα κατάταξης συνόλων, δίδεται ένα σύνολο από διαφορετικές κατατάξεις (π.χ. τα αποτελέσματα από διαφορετικές μηχανές αναζήτησης ιστοσελίδων σε ένα συγκεκριμένο ερώτημα) για το ίδιο σύνολο δεδομένων (π.χ. ιστοσελίδες σχετικές με το ερώτημα), και ο σκοπός είναι να επιλεγεί μια μοναδική κατάταξη που είναι κοντά σε όλες τις κατατάξεις σύμφωνα με ένα καλώς ορισμένο κριτήριο. Σε αυτό το παράδειγμα, οι διαφορετικές μηχανές αναζήτησης είναι οι ψηφοφόροι και κάθε σελίδα αντιστοιχεί σε ένα υποψήφιο, και ο σκοπός σύμφωνα με το οποίον υπολογίζεται η μοναδική κατάταξη είναι ο κανόνας ψηφοφορίας. Είναι φανερό ότι σε τέτοιες εφαρμογές η απόφαση για το ποιος είναι ο νικητής των εκλογών δεν είναι το μόνο πρόβλημα, συνήθως απαιτείται η πλήρης κατάταξη των υποψηφίων. Στην εργασία αυτή γίνεται αρχικά μια προσπάθεια καταγραφής των κυριότερων συστημάτων κοινωνικής επιλογής. Κατά κύριο λόγο εστιάζουμε στη μέθοδο που πρότεινε ο Dodgson και ακολούθως στην μέθοδο του Young. Αυτοί οι κανόνες ψηφοφορίας έχουν σχεδιαστεί για να βρίσκουν τον υποψήφιο που είναι πιο κοντά στο νικητή κατά Condorcet.
Το σκορ ενός δεδομένου υποψηφίου είναι γνωστό ότι είναι δύσκολο να υπολογιστεί και για τους δυο κανόνες. Σε αυτήν την εργασία, προτείνουμε για την μέθοδο του Dodgson δυο προσεγγιστικούς αλγόριθμους. Πιο συγκεκριμένα παρουσιάστηκαν και αναλύθηκαν δυο προσεγγιστικοί αλγόριθμοι υπολογισμού του Dodgson σκορ ενός υποψηφίου σε μία εκλογή Dodgson με N υποψηφίους, ένας άπληστος ντετερμινιστικός και ένας πιθανοτικός. Και οι δυο αλγόριθμοι έχουν λόγο προσέγγισης Ο (log N). Επίσης αποδεικνύουμε ότι ο άπληστος αλγόριθμος είναι βέλτιστος μέχρι ένα παράγοντα της τάξης του 2 εκτός αν όλα τα προβλήματα που ανήκουν στο ΝΡ έχουν υπο-εκθετικού (quasi-polynomial) χρόνου αλγορίθμους. Παρόλο που ο άπληστος αλγόριθμος είναι υπολογιστικά ισχυρότερος, ο πιθανοτικός μας αλγόριθμος έχει πλεονέκτημα υπό την οπτική της θεωρίας κοινωνικής επιλογής. Ακόμη, δείχνουμε ότι ο υπολογισμός οποιασδήποτε ικανοποιητικής προσέγγισης που παράγεται από τον κανόνα του Dodgson είναι υπολογιστικά δύσκολη. Αυτό παρέχει μια θεωρητική εξήγηση από σκοπιά υπολογιστικής πολυπλοκότητας για τις μεγάλες διαφορές που έχουν παρατηρηθεί στην θεωρία κοινωνικής επιλογής όταν συγκρίνονται οι εκλογές Dodgson με απλούστερους κανόνες ψηφοφορίας. Τέλος δείχνουμε ότι το πρόβλημα υπολογισμού του Young σκορ είναι ΝΡ-δύσκολο να προσεγγιστεί υπό οποιονδήποτε παράγοντα. Τα κυριότερα αποτελέσματα που εκπονήθηκαν σε αυτήν την εργασία παρουσιάστηκαν στο συνέδριο ACM-SIAM Symposium on Discrete Algorithms (SODA09).
|
|---|
