Metric distortion of voting rules with predictions

Abstract

Σε αυτή τη διπλωματική εργασία, μελετάμε την απόδοση των κανόνων ψηφοφορίας μετρώντας τη μετρική παραμόρφωσή τους και ενσωματώνουμε σε αυτούς προβλέψεις προκειμένου να επιτύχουμε καλύτερα αποτελέσματα. Έχουμε ένα σύνολο n ψηφοφόρων και ένα σύνολο m υποψηφίων οι οποίοι θεωρούμε ότι είναι τοποθετημένοι σε κάποιον μετρικό χώρο. Στόχος μας είναι να εκλέξουμε έναν υποψήφιο που ελαχιστοποιεί το κοινωνικό κόστος, δηλαδή το άθροισμα των αποστάσεων προς όλους τους ψηφοφόρους, έχοντας όμως πρόσβαση μόνο στις κατατάξεις προτιμήσεων των ψηφοφόρων και όχι στις πραγματικές τιμές των αποστάσεων. Η παραμόρφωση ενός κανόνα ψηφοφορίας μετρά τη χειρότερη δυνατή απόδοσή του σε σχέση με το βέλτιστο κοινωνικό κόστος. Παρουσιάζουμε αποτελέσματα από τη βιβλιογραφία, τα οποία παρέχουν φράγματα για τη μετρική παραμόρφωση αρκετών γνωστών κανόνων ψηφοφορίας, καθώς και έναν κανόνα ψηφοφορίας με βέλτιστη μετρική παραμόρφωση. Στη συνέχεια, μελετάμε το νέο μαθησιακά-ενισχυμένο πλαίσιο, όπου οι αλγόριθμοι χρησιμοποιούν προβλέψεις προερχόμενες από μηχανική μάθηση με στόχο να βελτιώσουν την απόδοσή τους. Αυτοί οι αλγόριθμοι αξιολογούνται με τις παραμέτρους της συνέπειας (απόδοση στην περίπτωση που η πρόβλεψη είναι σωστή) και της ευρωστίας (απόδοση στην περίπτωση που η πρόβλεψη είναι αυθαίρετα λανθασμένη). Χρησιμοποιώντας το μαθησιακά-ενισχυμένο πλαίσιο, αποδεικνύουμε φράγματα για την συνέπεια και την ευρωστία κανόνων ψηφοφορίας. Εστιάζουμε στο πρόβλημα της εκλογής επιτροπών με k-μέλη στην πραγματική ευθεία, όπου εκλέγονται k ≥ 3 υποψήφιοι και το κόστος κάθε ψηφοφόρου για μια επιτροπή ορίζεται ως η απόστασή του από το πλησιέστερο μέλος της επιτροπής. Προηγούμενες εργασίες δείχνουν ότι η παραμόρφωση για αυτό το πρόβλημα δεν είναι φραγμένη και ότι O(k) ερωτήματα για ακριβείς αποστάσεις είναι ικανά και αναγκαία για μια γραμμική (ως προς το πλήθος των ψηφοφόρων) παραμόρφωση. Ο αλγόριθμός μας χρησιμοποιεί προβλέψεις σχετικά με τη βέλτιστη επιτροπή και επιτυγχάνει σταθερή συνέπεια και γραμμική ευρωστία με O(k) ερωτήματα για ακριβείς αποστάσεις.