Dokument: Wahlbetrug mit festen und variablen Präferenzen: Eine Komplexitätsanalyse von Kontroll- und Bestechungsproblemen

Titel:	Wahlbetrug mit festen und variablen Präferenzen: Eine Komplexitätsanalyse von Kontroll- und Bestechungsproblemen
Weiterer Titel:	Election Fraud with Fixed and Variable Preferences: A Complexity Analysis of Control and Bribery Problems
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=56124
URN (NBN):	urn:nbn:de:hbz:061-20210503-074507-9
Kollektion:	Dissertationen
Sprache:	Deutsch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Maushagen, Cynthia [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 432,2 KB in einer Datei [ZIP-Datei erzeugen] Dateien vom 27.04.2021 / geändert 27.04.2021
Beitragende:	Prof. Dr. Rothe, Jörg [Gutachter] [im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen] Jun.-Prof. Dr. Baumeister, Dorothea [Gutachter] [im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen]
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:	In der vorliegenden Dissertation werden verschiedene Kontroll- und Bestechungsprobleme mit Hilfe der klassischen und parametrisierten Komplexitätstheorie untersucht, die sich aus dem Kontext von Wahlen ergeben. Dabei zeichnet sich ein Kontrollproblem dadurch aus, dass der Wahlleiter einer Wahl deren Ergebnis durch Veränderung der Wahlstruktur ändern möchte. Bei Bestechungsproblemen wiederum geht man, wie zu vermuten ist, davon aus, dass einzelne Wähler mittels Bestechung durch einen externen Agenten dazu gebracht werden, ihre Stimme nach dem Willen des Agenten zu ändern. Bei Bestechungsproblemen sind die Präferenzen also variabel, während diese bei Kontrollproblemen fest sind und sich lediglich die Struktur der Wahl verändern lässt. Für die Wahlregeln Veto und Maximin untersuchen wir mit Hilfe der klassischen Komplexitätstheorie zwei Gruppen von Kontrollproblemen. Während in der ersten Gruppe Probleme zur Partitionierung der Wählermenge betrachtet werden, werden in der zweiten Gruppe Probleme zur Partitionierung der Kandidatenmenge betrachtet. Je nach Gruppe teilt der Wahlleiter die Wähler bzw. Kandidaten in zwei Gruppen auf. Um als Sieger aus einer solchen Wahl hervorzugehen, muss sich ein Kandidat in einer Vorrunde und einem Finale gegen die Gewinner der anderen Vorrunde bewähren. Wir zeigen, dass die untersuchten Kontrollprobleme für die Wahlregel Maximin NP-vollständig sind. Für Veto teilen sich die Ergebnisse in NP-Vollständigkeitsresultate und effiziente Algorithmen auf. Danach widmen wir uns der Wahlregel Plurality und betrachten ein Kontrollproblem aus Sicht der parametrisierten Komplexitätstheorie. Bei diesem Kontrollproblem nehmen wir an, dass der Wahlleiter die Möglichkeit hat, weitere Kandidaten an der Wahl teilnehmen zu lassen. Wir analysieren dazu einen fehlerhaften Beweis aus der Literatur zur W[1]-Härte und können mit Hilfe eines neuen Beweises die W[1]-Härte nachweisen. Im Anschluss untersuchen wir für insgesamt acht iterative Wahlregeln das Bestechungsproblem Shift-Bribery. Bei diesem Problem gehen wir davon aus, dass der eingangs erwähnte Agent mit einem gewissen Budget zur Bestechung der Wähler ausgestattet ist. Dabei darf der Agent nur die Position eines ausgewählten Kandidaten relativ zu den anderen Kandidaten verändern. Die Kosten für die Veränderung der Stimme eines Wähler ergeben sich hierbei über einen individuell festgelegten Preis, der für jede paarweise Vertauschung zweier Kandidaten veranschlagt wird. Dabei stellt sich heraus, dass dieses Problem für alle untersuchten Wahlregeln NP-vollständig ist. In this thesis, various control and bribery problems that arise from the context of elections are investigated with the help of classical and parameterized complexity theory. A control problem is characterized by the ability of the election chair to change the result of an election by changing the election structure. In the case of bribery problems, it is assumed that individual voters are bribed by an external agent to change their votes according to the agent's preference. While the voting structure is variable in the case of control problems, the preferences of the voters are variable in the case of bribery problems. For the voting rules Veto and Maximin we consider two groups of control problems with the help of classical complexity theory. The first group deals with problems where the election chair is able to split the set of voters into two sets whereas in the second group he is able to split the set of candidates into two sets. In each case, the election chair creates two first-round subelections that determine which candidate takes part in a final round. We show that for Maximin all considered control problems are NP-complete. In contrast to that, we receive NP-completeness results as well as efficient algorithms for Veto. Afterwards, by giving a counterexample we observe that a reduction from the literature showing the W[1]-hardness of control by adding candidates to plurality elections, parameterized by the number of voters, is technically flawed, and we show how this reduction can be adapted to make it correct. Finally, we study the shift-bribery problem for eight iterative voting systems. In this problem, we assume that an agent has a certain budget to bribe the voters. Further, we assume that the agent is only allowed to change the position of a designated candidate relative to the other candidates. The costs for changing the preference of a voter result from an individually determined price for every swap of two candidates. We show that this problem is NP-complete for all considered voting systems.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Computational Complexity Theory/Cryptology
Dokument erstellt am:	03.05.2021
Dateien geändert am:	03.05.2021
Promotionsantrag am:	16.02.2021
Datum der Promotion:	15.04.2021