Βιβλιοθήκη ΟΠΑ - Ψηφιακό Αποθετήριο

ΠΥΞΙΔΑ Ιδρυματικό Αποθετήριο
και Ψηφιακή Βιβλιοθήκη

Όνομα χρήστη
Κωδικός πρόσβασης

Συλλογές :	Ιδρυματικό Αποθετήριο ΟΠΑ / AUEB Institutional Repository Σχολή Οικονομικών Επιστημών / School of Economics Τμήμα Οικονομικής Επιστήμης / Department of Economics Μεταπτυχιακές Εργασίες / Postgraduate dissertations

Τίτλος :	Algorithmic complexity as a barrier to voting manipulation

Εναλλακτικός τίτλος :	Η χρήση της αλγοριθμικής πολυπλοκότητας ως φράγμα στη χειραγώγηση ψηφοφοριών

Δημιουργός :	Φετάνης, Στυλιανός Fetanis, Stylianos

Συντελεστής :	Arvanitis, Stylianos (Επιβλέπων καθηγητής) Economides, George (Εξεταστής) Kammas, Pantelis (Εξεταστής) Athens University of Economics and Business, Department of Economics (Degree granting institution)

Τύπος :	Text

Φυσική περιγραφή :	67p.

Γλώσσα :	en

Αναγνωριστικό :	http://www.pyxida.aueb.gr/index.php?op=view_object&object_id=10671

Περίληψη :	Αυτή η διατριβή απαντά στο ερώτημα εάν η υπολογιστική πολυπλοκότητα που χαρακτηρίζει οποιονδήποτε αλγόριθμο χειραγώγησης εκλογών θα μπορούσε να αποτελέσει και εμπόδιο μιας τέτοιας απόπειρας. Πρώτον, εντοπίζουμε το κύριο πρόβλημα που προκύπτει στον τομέα της Θεωρίας Κοινωνικής Επιλογής που επιτρέπει τη στρατηγική συμπεριφορά και αλλοιώνει τις προκύπτουσες συναρτήσεις κοινωνικής ευημερίας. Το αποτέλεσμα αυτό επεκτείνεται στη συνέχεια και στις ψηφοφορίες, ως μέσο αποκάλυψης της ιεράρχησης που προκύπτει από μια συνάρτηση κοινωνικής ευημερίας. Δεύτερον, ορίζουμε την απαιτούμενη γλώσσα που θα χρησιμοποιήσουμε για να μελετήσουμε την υπολογιστική πολυπλοκότητα των αλγορίθμων σε όλη την υπόλοιπη διατριβή. Ορίζουμε τις έννοιες της αλγοριθμικής πολυπλοκότητας και των προβλημάτων NPc στην επιστήμη των υπολογιστών. Στη συνέχεια, χρησιμοποιώντας αυτή την γλώσσα, μελετάμε πόσο υπολογιστικά δύσκολη μπορεί να είναι μια χειραγώγηση σε μια ποικιλία κανόνων και συνθηκών ψηφοφορίας (όπως με σταθμισμένες, ή χωρίς σταθμισμένες ψήφους) δείχνοντας ότι, θεωρητικά, η χειραγώγηση μπορεί να είναι "δύσκολη". Ωστόσο, σύντομα συνειδητοποιούμε ότι τέτοια αποτελέσματα βασίζονται κυρίως σε σπάνιες περιπτώσεις και μετατοπίζουμε την προσοχή μας στις περιπτώσεις που είναι πιθανό να συναντήσουμε συχνότερα και μελετάμε πώς μπορούμε να εργαστούμε με κατά προσέγγιση λύσεις. Τέτοιες λύσεις λειτουργούν αρκετά καλά στις περισσότερες περιπτώσεις, γεγονός που δείχνει ότι πρέπει να είμαστε προσεκτικοί όταν χρησιμοποιούμε τα θεωρητικά αποτελέσματα που αναφέρονται παραπάνω. Τέλος, εφαρμόζουμε τις έννοιες και τη γλώσσα που κατασκευάσαμε σε όλη αυτή τη διατριβή στο σύστημα ψηφοφορίας που χρησιμοποιείται στις ελληνικές αυτοδιοικητικές εκλογές (τουλάχιστον μέχρι και το 2019). Μελετάμε πιθανές στρατηγικές χειραγώγησης με βεβαιότητα και υπό αβεβαιότητα. 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). Μελετάμε πιθανές στρατηγικές χειραγώγησης με βεβαιότητα και υπό αβεβαιότητα.
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.

Λέξη κλειδί :	Ψηφοφορία Πολυπλοκότητα Χειραγώγηση Αλγόριθμοι Προσομοίωση Voting Complexity Manipulation Algorithms Simulation

Διαθέσιμο από :	2023-08-25 10:03:58

Ημερομηνία έκδοσης :	28-03-2023

Ημερομηνία κατάθεσης :	2023-08-25 10:03:58

Δικαιώματα χρήσης :	Free access

Άδεια χρήσης :

Αρχείο: Fetanis_2023.pdf

Τύπος: application/pdf

Είσοδος