Back to search

Athens University Economics and Business (AUEB)

Algorithmic and game-theoretic aspects of computational social choice

Abstract

dc:description

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.

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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/57970

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Papasotiropoulos, Georgios; Παπασωτηρόπουλος, Γεώργιος. Algorithmic and game-theoretic aspects of computational social choice. Athens University Economics and Business (AUEB), 2024. http://hdl.handle.net/10442/hedi/57970