Metric Distortion of Committee Election on Perturbation Stable Instances

Abstract

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