Συγκριτική Αξιολόγηση Κανόνων Ψηφοφορίας Για Την Εκλογή Επιτροπών

Abstract

Η υπολογιστική θεωρία της κοινωνικής επιλογής είναι ένας πρόσφατα δημιουργηθείς κλάδος της θεωρητικής επιστήμης των υπολογιστών, που μελετάει την υπολογιστική πολυπλοκότητα σε προβλήματα ψηφοφοριών. Αυτή η περιοχή έχει προσελκύσει το ενδιαφέρον των ερευνητών τα τελευταία χρόνια λόγω των ποικίλων εφαρμογών της σε εκλογές, στην εύρεση των επικρατέστερων υποψηφίων, στα συστήματα προτάσεων κλπ.Στόχος αυτής της διπλωματικής εργασίας είναι η διεξοδική πειραματική αξιολόγηση των κανόνων ψηφοφορίας για την εκλογή επιτροπών που χρησιμοποιούνται στις προαναφερθείσες εφαρμογές. Για τον λόγο αυτό υλοποιήσαμε τους πιο διάσημους κανόνες εκλογής επιτροπών - SNTV, STV, Bloc, $k$-Borda,Chamberlin-Courant, Monroe - και τους αξιολογήσαμε με γνώμονα ιδιότητες που αποζητώνται στα αποτελέσματα των εφαρμογών (π.χ. ποικιλομορφία, αναλογική αντιπροσωπευτικότητα κλπ.). Σκοπός μας είναι η πλήρης κατανόηση και εύρεση των πλέον κατάλληλων κανόνων για τις παραπάνω εφαρμογές. Για να το πετύχουμε αυτό, εκτελούμε αρχικά ένα πείραμα εκλογών στο δισδιάστατο χώρο,έτσι ώστε να υπάρχει η δυνατότητα οπτικοποίησης τόσο των προτιμήσεων των ψηφοφόρων και όσο και των αποτελεσμάτων των κανόνων.Επιπλέον, σχεδιάζουμε και υλοποιούμε αποδοτικούς ευρεστικούς αλγορίθμους για τους κανόνες που υπολογιστικά ανήκουν στο NP (Chamberlin-Courant και Monroe), αξιολογούμε τα αποτελέσματα και σχολιάζουμε τις αδυναμίες των αλγορίθμων μας. Στη συνέχεια, αξιολογούμε τους κανόνες και τους αλγορίθμους μας σύμφωνα με την ικανότητα τους να βρίσκουν ευσταθείς επιτροπές. Μελετάμε αν το αποτέλεσμα τουςμπορεί να επηρεαστεί από την ελεγχόμενη μεταφορά ή από την προσθήκη ενός ψηφοφόρου. Ερμηνεύουμε τα αποτελέσματά μας σύμφωνα με τις έννοιες της χειραγώγησης, του ελέγχου και της αποκάλυψης πληροφοριών για τον επιπλέον ψηφοφόρο.Τέλος, σχεδιάζουμε ένα πείραμα για την μελέτη δεδομένων προερχόμενων από πραγματικές ψηφοφορίες. Περιγράφουμε τη λογική που κρύβεται πίσω από τις σχεδιαστικές μας αποφάσεις και πώς η δυσκολία εύρεσης κατάλληλων δεδομένων γιατην μελέτη κανόνων όπως οι Chamberlin-Courant και Monroe, οδηγεί την έρευνα μας σε διαφορετικά μονοπάτια.