Algorithmic and game-theoretic aspects of computational social choice

Abstract

The present dissertation aims to explore innovative decision-making approaches that complement traditional voting processes, examining them through an algorithmic, game-theoretic and axiomatic lens. The central objective is to identify voting procedures that can increase agents’ desire to participate in collective governance and improve voters’ participation experience. Therefore, we focus on suggesting and analysing voting frameworks and election rules that reconcile the varying preferences of the electorate towards achieving socially desirable outcomes in various scenarios, aspiring to elevate both the quantity and quality of community involvement in democratic processes. The doctoral thesis addresses two primary challenges of Computational Social Choice:--- The first part concerns elections with a combinatorial structure, where a decision must be made over a set of interdependent issues of multiple alternatives each. In such scenarios, voters cast conditional approval ballots which enable them to express (approval) preferences for issues that are contingent on the outcome of others. We first focus on the winner determination problem under the natural voting rule that minimizes voters’ total dissatisfaction, referred to as Conditional Minisum. We present positive and negative results for approximate and parameterized algorithms. Additionally, we investigate the robustness of the rule against the malicious actions of adding or deleting voters or alternatives, in terms of computational complexity. Finally, we introduce and study two further voting rules: Conditional Proportional ApprovalVoting and Conditional Method of Equal Shares. These are inferior to Minisum with respect to the total satisfaction score but, in contrast to Minisum, are able to ensure strong proportionality guarantees.--- In the second part, we focus on the concept of Delegative Voting, which strikes a balance between direct and representative democracy. Flexible and dynamic voting frameworks that empower voters to choose their preferred mode of participation are designed and analysed. First, we propose a framework that allows voters to express approval preferences not only for casting a ballot themselves or abstaining but also forbeing represented by specific sets of other voters. We then examine the problems of minimizing (resp. maximizing) the number of dissatisfied (resp. satisfied) voters from the perspectives of computational complexity, parameterized and approximate algorithms. Secondly, we study a delegative voting framework in which we incorporate a temporal dimension to address adaptations of voters’ preferences over time, towards mitigating vote loss: a critical concern for Delegative Voting settings. Finally, we explore the potential enhancement of electorate’s satisfaction through ballot delegation, in scenarios where voters have incomplete preferences and we establish necessary and sufficient conditions for achieving a socially better outcome –compared to direct voting– by leveraging the participation of proxies.

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