Algorithmic and game-theoretic aspects of computational social choice
Authors: Παπασωτηρόπουλος Γεώργιος 
Published: December 2024

Η παρούσα διδακτορική διατριβή αποσκοπεί στη διερεύνηση καινοτόμων προσεγγίσεων λήψης αποφάσεων που συμπληρώνουν τις παραδοσιακές διαδικασίες ψηφοφορίας, εξετάζοντάς τες από τη σκοπιά των αλγορίθμων, της θεωρίας παιγνίων και της αξιωματικής θεμελίωσης. Ο κεντρικός σκοπός είναι να προσδιοριστούν και να αναλυθούν εκλογικές διαδικασίες που μπορούν να αυξήσουν την επιθυμία των ατόμων για συμμετοχήστη συλλογική διακυβέρνηση και να βελτιώσουν την εμπειρία της συμμετοχής των ψηφοφόρων. Στοχεύοντας σε κοινωνικά επιθυμητά αποτελέσματα για μια σειρά διαφορετικών σεναρίων, φιλοδοξούμε να βελτιώσουμε ποσοτικά και ποιοτικά τη συμμετοχή του κοινού στις δημοκρατικές διαδικασίες. Η διατριβή επικεντρώνεται σε δύο βασικές προκλήσεις της Υπολογιστικής Θεωρίας Κοινωνικής Επιλογής:--- Το πρώτο μέρος επικεντρώνεται σε εκλογές με συνδυαστική δομή όπου απαιτείται η λήψη αποφάσεων για πολλαπλά αλληλοεξαρτώμενα ζητήματα για τα οποία οι ψηφοφόροι έχουν τη δυνατότητα να εκφράσουν προτιμήσεις εξαρτώμενες από την έκβαση άλλων ζητημάτων. Επικεντρωνόμαστε αρχικά στο πρόβλημα εύρεσης νικητή για κάθε ένα από τα ζητήματα, υπό τον φυσικό κανόνα ψηφοφορίας που ελαχιστοποιεί τη συνολική δυσαρέσκεια των ψηφοφόρων (Conditional Minisum). Παρουσιάζουμε θετικά και αρνητικά αποτελέσματα για προσεγγιστικούς και παραμετρικούς αλγορίθμους. Επιπλέον, διερευνούμε την ανθεκτικότητα του κανόνα έναντι των κακόβουλων ενεργειών προσθήκης ή διαγραφής ψηφοφόρων ή προσθήκης ή διαγραφής επιλογών σε ορισμένα ζητήματα, εξετάζοντας την υπολογιστική πολυπλοκότητα των αντίστοιχων προβλημάτων. Τέλος, εισάγουμε και μελετάμε τους κανόνες ψηφοφορίας Conditional Proportional Approval Voting και Conditional Method of Equal Shares. Αυτοί οι κανόνες είναι υποδεέστεροι του Minisum ως προς τη συνολική ικανοποίηση των ψηφοφόρων αλλά, σε αντίθεση με τον Minisum, εξασφαλίζουν ισχυρές εγγυήσεις αναλογικής εκπροσώπησης.--- Στο δεύτερο μέρος, εστιάζουμε στην έννοια του Delegative Voting, η οποία συνδυάζει χαρακτηριστικά άμεσης και αντιπροσωπευτικής δημοκρατίας. Σχεδιάζονται και αναλύονται ευέλικτα, δυναμικά μοντέλα εκλογών, τα οποία δίνουν στους ψηφοφόρους τη δυνατότητα να επιλέξουν τον προτιμώμενο τρόπο συμμετοχής τους στη διαδικασία. Αρχικά, προτείνουμε ένα πλαίσιο που επιτρέπει στους ψηφοφόρους να εκφράζουν τις προτιμήσεις τους όχι μόνο σχετικά με την καταχώρηση ψήφου από τους ίδιους αλλά και σχετικά με την εκπροσώπηση από ορισμένα σύνολα άλλων ψηφοφόρων. Έπειτα αναλύουμε τα προβλήματα ελαχιστοποίησης (αντίστοιχα μεγιστοποίησης) του αριθμού των δυσαρεστημένων (αντίστοιχα ικανοποιημένων) ψηφοφόρων από την οπτική της υπολογιστικής πολυπλοκότητας, των παραμετρικών και των προσεγγιστικών αλγορίθμων. Επίσης, μελετάμε ένα πλαίσιο ψηφοφορίας το οποίο ενσωματώνει τη χρονική διάσταση για να αντιμετωπιστούν προσαρμογές των προτιμήσεων των ψηφοφόρων που πιθανώς συμβαίνουν κατά την πάροδο του χρόνου, με απώτερο σκοπό τη μείωση της απώλειας ψήφων: ένα κρίσιμο μειονέκτημα γνωστών μοντέλων Delegative Voting. Τέλος, εστιάζουμε στην ενίσχυση της ικανοποίησης των ψηφοφόρων μέσω ανάθεσης της ψήφου, σε σενάρια στα οποία οι ψηφοφόροι δεν έχουν σχηματίσει πλήρη γνώμη για όλα τα προς ψήφιση ζητήματα και προσδιορίζουμε αναγκαίες και ικανές συνθήκες για την επίτευξη ενός κοινωνικά ικανοποιητικού αποτελέσματος.