Dokument: Deciding the Uncertain: Axiomatic Aspects of Fair Division and Computational Complexity Studies in Computational Social Choice and Graph Theory
| Titel: | Deciding the Uncertain: Axiomatic Aspects of Fair Division and Computational Complexity Studies in Computational Social Choice and Graph Theory | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=59770 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20220608-112122-5 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Weishaupt, Robin [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Prof. Dr. Rothe, Jörg-Matthias [Betreuer/Doktorvater] Jun.-Prof. Dr. Baumeister, Dorothea [Betreuer/Doktorvater] [im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen] | |||||||
| Stichwörter: | Computer Science Computational Complexity Theory Graph Theory Computational Social Choice Fair Division | |||||||
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
| Beschreibung: | In this work we study uncertainty across four different areas of theoretical computer science. For three of the four areas, we analyze the hardness of new and existing problems with tools from computational complexity theory. For the fourth area, we inspect its fundamental axioms, identify discrepancies, and suggest improvements. The four areas we address are judgment aggregation, preference aggregation by voting, fair division of divisible goods, and stability of graphs.
Judgment aggregation studies the aggregation of individual judges’ judgments over a given agenda via some aggregation rule into a collective outcome. In our work we study a generalized family of sequential judgment aggregation rules. A sequential judgment aggregation rule aggregates a set of judgments into a collective outcome by following a specified order over the elements of the agenda. With this family of rules defined, we determine the computational complexity of several uncertainty-related decision problems for these rules. Among the studied problems are the classical winner problem as well as problems addressing manipulability. In preference aggregation by voting, we are given a set of candidates and a set of voters expressing their preference orders over the candidates. Using a predefined voting rule, we determine one or multiple winners for such an election by aggregating the voters’ preferences. In our work, we introduce a novel variant of the possible winner problem, the possible winner with uncertain weights problem. In this problem one is given a set of candidates, a distinguished candidate, and a set of votes over the candidates with uncertain weights. One is asked whether there is a weight allocation to the votes such that the distinguished candidate wins the weighted election. We define a framework to study the computational complexity of the problem and three further variants for integer and rational weights as well as several voting rules. The area of fair division of divisible goods is also called cake-cutting. Its general setting consists of an arbitrarily divisible good and a set of players with preferences over the good, willing to split the good among themselves. Giving the area its name, a cake is used as a metaphor for the good and an interactive cake-cutting procedure portions the cake among the players. In our work, we study basic axioms of cake-cutting: What pieces of cake should be considered as valid pieces, such that every player can evaluate them. We survey current cake-cutting literature, identify discrepancies, and make suggestions supported by the means of measure theory. Stability of graphs belongs to the area of graph theory. Given a graph and a graph parameter, a graph is called stable with respect to this parameter if removing any single edge of the graph does not alter the parameter’s value. Similar concepts are defined for vertices and adding edges and vertices. We build on already defined decision problems in this field and study the complexity of these stability related problems for special graph classes. In total, we cover the graph classes of trees, forests, bipartite graphs, and co-graphs as well as four well-known graph parameters. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Computational Complexity Theory/Cryptology | |||||||
| Dokument erstellt am: | 08.06.2022 | |||||||
| Dateien geändert am: | 08.06.2022 | |||||||
| Promotionsantrag am: | 17.03.2022 | |||||||
| Datum der Promotion: | 30.05.2022 |
