Athens University Economics and Business (AUEB)
Algorithmic and game-theoretic aspects of computational social choice
Abstract
dc:descriptionThe 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.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2024
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Papasotiropoulos, Georgios
- Παπασωτηρόπουλος, Γεώργιος
Subjects
dc:subject × 10- Υπολογιστική θεωρία κοινωνικής επιλογής
- Αλγόριθμοι και υπολογιστική πολυπλοκότητα
- Computational social choice
- Algorithms and computational complexity
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
- Computer and Information Sciences
- Natural Sciences
- Computer science, theory and methods
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/57970