Dokument: COMSOC Methods in Real-World Applications

Titel:	COMSOC Methods in Real-World Applications
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=63129
URN (NBN):	urn:nbn:de:hbz:061-20230713-110451-2
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Laußmann, Christian [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 3,69 MB in einer Datei [ZIP-Datei erzeugen] Dateien vom 10.07.2023 / geändert 10.07.2023
Beitragende:	Prof. Dr. Rothe, Jörg [Betreuer/Doktorvater] Jun.-Prof. Dr. Baumeister, Dorothea [Gutachter] [im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen]
Stichwörter:	COMSOC, Networks, Centrality, Participatory Budgeting, Apportionment, Approval Voting, Approval Ballots, Voting
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:	Computational social choice (COMSOC) is a research area focussed on the design and analysis of algorithms for collective decision tasks. In this thesis, we focus on one sub-area of the field: voting. We study four (near) real-world applications of voting. First, we show how voting can be used in networks to find central individual nodes, or sets of nodes. We show that network science, and voting theory overlap, and each can be informed by the other. Second, we study participatory budgeting. This is an application of voting where voters vote on projects they would like to fund, while external conditions such as time and cost limits must be satisfied. Participatory budgeting is not new to literature. However, we introduce a twist: project costs, and/or project durations are uncertain. This introduces additional difficulties to the planning process. The third part of this thesis deals with strategic campaigns in apportionment elections where an external agent tries to influence the election by bribing/convincing voters to change their vote. We show that computing optimal bribery actions is generally easy with an efficient algorithm we develop. This is arguably also a negative result as it means that apportionment elections could be susceptible to such campaigns. Thus, we also propose an extension to apportionment elections which makes the procedures computationally resistant to strategic campaigns. Lastly, we develop a new ballot format for multiwinner elections which helps voters state more sophisticated preferences with ease. More specifically, the ballots allow expressing approval, incompatibilities, substitution effects, and dependencies. Computational social choice (COMSOC) ist ein Forschungsbereich, der sich auf die Entwicklung und Analyse von Mechanismen zur kollektiven Entscheidungsfindung fokussiert. In dieser Doktorarbeit behandeln wir einen besonderen Bereich von COMSOC: Wahlen. Insbesondere behandeln wir vier Anwendungen von Wahlmethoden, die besonders nah an realen Anwendungen sind. Als erstes zeigen wir, wie Wahlmethoden verwendet werden können, um zentrale Knoten (oder Knotenmengen) in Netzwerken zu identifizieren. Unsere Ergebnisse legen nahe, dass Wahltheorie und Netzwerktheorie eine große gemeinsame Schnittmenge haben, und dass beide voneinander profitieren können. Als nächstes betrachten wir participatory budgeting (zu Deutsch: Bürgerhaushalte), wo Wähler über Projekte abstimmen, die in einer Stadt gebaut werden sollen. Dabei gibt es Beschränkungen bezüglich des Budgets und der Zeit, die für die Umsetzung der Projekte zur Verf¨ugung stehen. Participatory budgeting ist nicht neu. Wir versuchen in dieser Arbeit aber, das Modell realistischer zu machen, indem wir unsichere Projektkosten und Realisierungszeiten erlauben. Durch die Unsicherheiten wird der Planungsprozess erschwert. Im dritten Teil dieser Doktorarbeit kümmern wir uns um strategische Wahlkampagnen in Parlamentswahlen. Hier versucht ein externer Agent, den Ausgang der Wahl (d.h. die Sitzverteilung) zu seinen Gunsten zu ändern, indem gezielt bestimmte Wähler überzeugt (oder bestochen) werden, ihre Stimme zu ändern. Wir entwickeln einen effizienten Algorithmus, der optimale Wahlkampagnen berechnen kann. Dies ist nicht unbedingt ein positives Ergebnis, da es möglicherweise die Manipulation einer Wahl erleichtert. Wir stellen daher auch eine kleine Erweiterung für parlamentarische Wahlsysteme vor, die die Berechnungskomplexität solcher Kampagnen signifikant erschwert. Zuletzt entwickeln wir ein neuartiges Stimmzettelformat, welches die Stimmabgabe bei komplizierteren Präferenzen in Komiteewahlen erleichtert. Unser Format ermöglicht die Angabe und Auswertung von u.a. Abhängigkeiten und Inkompatibilitäten zwischen Kandidaten.
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:	13.07.2023
Dateien geändert am:	13.07.2023
Promotionsantrag am:	05.04.2023
Datum der Promotion:	04.07.2023