Dokument: From Individual to Collective: Exploring Multiwinner Elections, Participatory Budgeting, and Judgment Aggregation on a Local and Global Level
| Titel: | From Individual to Collective: Exploring Multiwinner Elections, Participatory Budgeting, and Judgment Aggregation on a Local and Global Level | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=66045 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20240610-091135-1 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Boes, Linus Leopold [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Jun.-Prof. Dr. Baumeister, Dorothea [Gutachter] [im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen] Prof. Dr. Rothe, Jörg-Matthias [Gutachter] | |||||||
| Stichwörter: | Computer Science, Computational Social Choice, Multiwinner Elections, Participatory Budgeting, Judgment Aggregation | |||||||
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
| Beschreibung: | In this thesis, we explore three structurally close frameworks for aggregating individual (approval-based) preferences into a collective outcome, namely multiwinner elections, participatory budgeting, and judgment aggregation. Located at the core of computational social choice, we study aggregation mechanisms for multiagent decision-making processes from a computational point of view, using tools and techniques from theoretical computer science and artificial intelligence. In the respective settings, a set of agents decides, which subset of predefined alternatives should appear in a collective outcome. For this purpose, each agent provides an individual binary evaluation on whether each distinct alternative should be selected. A constraint limits the set of feasible outcomes and a voting rule maps the agents' preferences to at least one feasible set of winning alternatives.
Motivated by different practical applications, the three aforementioned frameworks can be informally distinguished as follows. In multiwinner elections, voters elect a fixed-size committee of candidates. In participatory budgeting, citizens decide over the spending of limited public funds on a selection of projects, each having a predefined cost for implementation. In judgment aggregation, a set of judges must come to a (logically consistent) agreement over the truthfulness of a set of logically interconnected propositions. Overall, the key results acquired in this thesis can be grouped into five categories: An (i) axiomatic analysis, helps understanding the behavior of voting rules and their limitations. Notably, we develop multiple impossibility results (stating that some properties cannot be satisfied simultaneously by any voting method) and discuss potential ways to partly escape those negative results. To select a voting rule that can realistically be used in an election (by computing an outcome in a reasonable amount of time), it is important to study the (ii) computational complexity of winner determination in the first place. Our results for related decision problems range from efficiently computable algorithms to hardness in the second level of the polynomial-time hierarchy. Contrarily, if a voting rule is prone to some kind of (iii) manipulative interference, a high complexity for computing a beneficial manipulative action might render strategic behavior infeasible. Along with identifying the complexity for various related decision problems, we discuss ways to prevent manipulative actions for efficiently computable rules. We uncover several (iv) relationships between voting rules, linking problems that have been studied independently closer together. Lastly, we investigate the potential impact from considering a slightly generalized (v) ballot design. | |||||||
| Lizenz: |  Dieses Werk ist lizenziert unter einer Creative Commons Namensnennung 4.0 International Lizenz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Computational Complexity Theory/Cryptology | |||||||
| Dokument erstellt am: | 10.06.2024 | |||||||
| Dateien geändert am: | 10.06.2024 | |||||||
| Promotionsantrag am: | 06.03.2024 | |||||||
| Datum der Promotion: | 19.04.2024 |
