Συλλογές
Τίτλος Algorithmic complexity as a barrier to voting manipulation
Εναλλακτικός τίτλος Η χρήση της αλγοριθμικής πολυπλοκότητας ως φράγμα στη χειραγώγηση ψηφοφοριών
Δημιουργός Φετάνης, Στυλιανός, Fetanis, Stylianos
Συντελεστής Kammas, Pantelis
Athens University of Economics and Business, Department of Economics
Economides, George
Arvanitis, Stylianos
Τύπος Text
Φυσική περιγραφή 67p.
Γλώσσα en
Αναγνωριστικό http://www.pyxida.aueb.gr/index.php?op=view_object&object_id=10671
Περίληψη This thesis is studying whether the computational complexity inherent in any election manipulation algorithm could become a barrier to strategic voting. Firstly, we identify the main problem arising in the field of Social Choice which allows for strategic behaviour that affects the resulting Social Welfare Function. This result is then extended to voting, as a means of obtaining the rankings of the Social Welfare Function. Secondly, we define the required language we will use to study the computational complexity of algorithms throughout the rest of the thesis. We introduce the concepts of time complexity and NPc problems in computer science. Then, using the appropriate language, we study how computationally hard a manipulation can be under a variety of voting schemes and voting conditions (such as weighted, or unweighted votes) showing that, theoretically, manipulation can be "hard". However, we soon realize that such results are mostly based on the worst of cases and we shift our focus on the average cases and study how we can work with approximate solutions. Such solutions work fairly well in most cases which shows that we should be cautious when using the theoretical results mentioned above. Finally, we apply the notions and language we constructed throughout this thesis on the Plurality with Runoff protocol. We study possible manipulations under certainty and under uncertainty.
Αυτή η διατριβή απαντά στο ερώτημα εάν η υπολογιστική πολυπλοκότητα που χαρακτηρίζει οποιονδήποτε αλγόριθμο χειραγώγησης εκλογών θα μπορούσε να αποτελέσει και εμπόδιο μιας τέτοιας απόπειρας. Πρώτον, εντοπίζουμε το κύριο πρόβλημα που προκύπτει στον τομέα της Θεωρίας Κοινωνικής Επιλογής που επιτρέπει τη στρατηγική συμπεριφορά και αλλοιώνει τις προκύπτουσες συναρτήσεις κοινωνικής ευημερίας. Το αποτέλεσμα αυτό επεκτείνεται στη συνέχεια και στις ψηφοφορίες, ως μέσο αποκάλυψης της ιεράρχησης που προκύπτει από μια συνάρτηση κοινωνικής ευημερίας. Δεύτερον, ορίζουμε την απαιτούμενη γλώσσα που θα χρησιμοποιήσουμε για να μελετήσουμε την υπολογιστική πολυπλοκότητα των αλγορίθμων σε όλη την υπόλοιπη διατριβή. Ορίζουμε τις έννοιες της αλγοριθμικής πολυπλοκότητας και των προβλημάτων NPc στην επιστήμη των υπολογιστών. Στη συνέχεια, χρησιμοποιώντας αυτή την γλώσσα, μελετάμε πόσο υπολογιστικά δύσκολη μπορεί να είναι μια χειραγώγηση σε μια ποικιλία κανόνων και συνθηκών ψηφοφορίας (όπως με σταθμισμένες, ή χωρίς σταθμισμένες ψήφους) δείχνοντας ότι, θεωρητικά, η χειραγώγηση μπορεί να είναι "δύσκολη". Ωστόσο, σύντομα συνειδητοποιούμε ότι τέτοια αποτελέσματα βασίζονται κυρίως σε σπάνιες περιπτώσεις και μετατοπίζουμε την προσοχή μας στις περιπτώσεις που είναι πιθανό να συναντήσουμε συχνότερα και μελετάμε πώς μπορούμε να εργαστούμε με κατά προσέγγιση λύσεις. Τέτοιες λύσεις λειτουργούν αρκετά καλά στις περισσότερες περιπτώσεις, γεγονός που δείχνει ότι πρέπει να είμαστε προσεκτικοί όταν χρησιμοποιούμε τα θεωρητικά αποτελέσματα που αναφέρονται παραπάνω. Τέλος, εφαρμόζουμε τις έννοιες και τη γλώσσα που κατασκευάσαμε σε όλη αυτή τη διατριβή στο σύστημα ψηφοφορίας που χρησιμοποιείται στις ελληνικές αυτοδιοικητικές εκλογές (τουλάχιστον μέχρι και το 2019). Μελετάμε πιθανές στρατηγικές χειραγώγησης με βεβαιότητα και υπό αβεβαιότητα.
Λέξη κλειδί Χειραγώγηση
Αλγόριθμοι
Προσομοίωση
Voting
Complexity
Manipulation
Algorithms
Simulation
Πολυπλοκότητα
Ψηφοφορία
Διαθέσιμο από 2023-08-25 10:03:58
Ημερομηνία έκδοσης 28-03-2023
Ημερομηνία κατάθεσης 2023-08-25 10:03:58
Δικαιώματα χρήσης Free access
Άδεια χρήσης https://creativecommons.org/licenses/by/4.0/