Dokument: From Election Fraud to Finding the Dream Team: A Study of the Computational Complexity in Voting Problems and Stability in Hedonic Games
| Titel: | From Election Fraud to Finding the Dream Team: A Study of the Computational Complexity in Voting Problems and Stability in Hedonic Games | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=37556 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20160317-105520-6 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Schend, Lena [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Prof. Dr. Rothe, Jörg [Gutachter] Prof. Dr. Niedermeier, Rolf [Gutachter] | |||||||
| Stichwörter: | Komplexitätstheorie, Computational Social Choice, Hedonic Games, Wahltheorie, Koalitionsbildung | |||||||
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
| Beschreibungen: | Die vorliegende Dissertation untersucht komplexitätstheoretische Eigenschaften verschiedener Wahlprobleme und kooperativer Spiele mit hedonischen Präferenzen.
Für die Wahlsysteme Bucklin Voting und Fallback Voting werden verschiedene Arten der Einflussnahme im Hinblick auf ihre Berechnungskomplexität untersucht. Wir präsentieren eine breite Analyse der beiden Wahlsysteme bezüglich der klassischen Berechnungskomplexität von Manipulation, Bestechung und des Swap-Bribery-Problems. Darüber hinaus untersuchen wir ebenfalls eine für das Wahlsystem Fallback Voting angepasste Variante von Extension Bribery. Hinsichtlich der Komplexität von Wahlkontrolle erweitern wir bereits bekannte Analysen, indem wir die parametrisierte Komplexität von Kontrolle durch Hinzufügen/Entfernen von Kandidaten oder Wählern betrachten, wobei der Parameter jeweils die Anzahl der hinzugefügten/entfernten Kandidaten bzw.\ Wähler ist. Ergänzend dazu präsentieren wir die erste experimentelle Untersuchung von Kontrollproblemen, in der wir die Berechnungskomplexität von Kontrolle in zufällig erzeugten Wahlen empirisch untersuchen. Neben Bucklin und Fallback Voting untersuchen wir in diesem Zusammenhang ebenfalls die Pluralitätsregel. Des Weiteren analysieren wir die Komplexität des Margin-of-Victory-Problems und untersuchen dessen Verhältnis zu destruktiver ungewichteter Bestechung und zeigen NP-Vollständigkeit dieser beiden Probleme für das Cup-Protokoll. Für die exakte Variante des Margin-of-Victory-Problems, die wir erstmals definieren und analysieren, zeigen wir DP-Vollständigkeit für das Schulze-System, das Cup-Protokoll und die Familie von Copeland-Systemen. Darüber hinaus definieren wir eine weitere Variante -- den Swap Margin of Victory – und zeigen dessen enge Verbindung zu der destruktiven Variante des Swap-Bribery-Problems mit Einheitspreisen. Für das Cup-Protokoll ist dieses Problem NP-vollständig, während wir für k-Approval und bestimmte Scoring-Protokolle Polynomialzeitalgorithmen angeben. Darüber hinaus führen wir eine neue Variante des Possible-Winner-Problems für gewichtete Wahlen ein, in denen die Präferenzen der Wähler vollständig gegeben, die Gewichte der Wähler jedoch unbestimmt sind. Für den Fall, dass die Gewichte aus den nicht-negativen rationalen Zahlen gewählt werden, zeigen wir, dass dieses Problem sowohl für Scoring-Protokolle als auch für Bucklin Voting und Fallback Voting in deterministischer Polynomialzeit lösbar ist. Für hedonische Spiele mit feind-basierten Präferenzen widmen wir uns der Komplexitätsanalyse der Probleme, für ein gegebenes solches Spiel zu entscheiden, ob eine wundervoll stabile bzw.\ strikt kernstabile Koalitionsstruktur existiert. Wir verbessern bekannte untere Schranken für diese Probleme und zeigen deren DP-Härte. Darüber hinaus ist es uns gelungen zu zeigen, dass ein coDP-Härte-Beweis gleichzeitig Härte für die Klasse „parallelen Zugriff auf NP“ impliziert. Damit wäre die exakte Komplexität des Existenzproblems bezüglich wundervoller Stabilität vollständig beschrieben, da dieses Problem bekanntermaßen in dieser Komplexitätsklasse enthalten ist. Außerdem führen wir eine neue Klasse hedonischer Spiele ein, in denen jeder Spieler seine Mitspieler in Freunde, Feinde und neutrale Spieler aufteilt und für die Menge der Freunde und der Feinde jeweils eine schwache Präferenzordnung angibt. Um diese Präferenzen über Spielern zu Präferenzen über Koalitionen zu erweitern, verwenden wir eine verallgemeinerte Bossong-Schweigert-Erweiterung. Da es in diesen FEN-hedonischen Spielen (FEN steht für „Friend/Enemy/Neutral“) jedoch unvollständige Präferenzen geben kann, also Paare von Koalitionen existieren können, die anhand dieser Präferenzen nicht vergleichbar sind, definieren wir sogenannte Vergleichbarkeitsfunktionen mit kardinalen Werten basierend auf Borda-ähnlichen Scoring-Vektoren. Für diese echte Unterklasse von additiv separablen hedonischen Spielen analysieren wir die Komplexität von Verifikations- und Existenzproblemen bezüglich vieler bekannter Stabilitätskonzepte wie der Nash-Stabilität oder der (strikten) Kernstabilität.In this thesis we study computational aspects of different voting problems and cooperative games with hedonic preferences. For two well-studied voting systems, namely Bucklin and fallback voting, we present a detailed study of the computational complexity of common manipulative attacks on elections. We fully describe the classical worst-case complexity of manipulation, bribery, and swap bribery in both voting systems and furthermore study extension bribery tailored to fallback elections. We extend existing studies of the complexity of electoral control in Bucklin and fallback elections by investigating control by adding/deleting candidates or voters parameterized by the number of added/deleted candidates or voters, respectively. We complement these results with the first experimental evaluation of electoral control based on randomly generated elections, which also provides results for plurality elections. Furthermore, we study the complexity of the margin of victory problem and its relation to destructive unweighted bribery. We show that for the cup rule, both destructive unweighted bribery and the margin of victory problem are NP-complete. Beyond that, we introduce and study two new variants of this problem: exact margin of victory and swap margin of victory. The exact variant can be shown to be DP-complete for the Schulze and the cup rule, as well as for the family of Copeland-systems. The swap margin of victory problem, on the other hand, can be shown to be solvable in deterministic polynomial time for k-approval and certain positional scoring rules, while for the cup rule this problem is NP-complete. We furthermore show the close connection of the swap margin of victory problem and destructive swap bribery with unit costs. Moreover, we define a new notion of the possible winner problem for weighted elections in which the uncertainty lies in the voters' weights and the complete preferences of the voters are given. We study this problem in detail for nonnegative rational weights and show that for positional scoring rules and Bucklin and fallback voting this problem can be solved in deterministic polynomial time. In the context of hedonic games we study the computational complexity of wonderful stability existence and strict core stability existence in enemy-based hedonic games. We improve the best known lower bounds for these problems by establishing DP-hardness results. We furthermore prove that coDP-hardness of these problems directly implies hardness for the class "parallel access to NP", which in turn would resolve the question of the exact complexity of the former problem, as it is known to be contained in this complexity class. Beyond that, we introduce a new class of hedonic games in which each player divides her co-players into friends, enemies, and other (neutral) players and furthermore provides a weak ranking of her friends and a weak ranking of her enemies. These preferences over players are extended to preferences over coalitions using a generalized Bossong-Schweigert extension principle. The thus defined FEN-hedonic games may have incomplete preferences, meaning that there can be pairs of coalitions that are incomparable with respect to this preference extension. We suggest to break these incomparabilities by defining cardinal comparability functions based on Borda-like scoring vectors leading to additively separable preferences. We show that this class of Borda-induced FEN-hedonic games is a strict subclass of additively separable hedonic games and provide a detailed study on the computational complexity of the existence and verification problems of commonly studied stability concepts such as Nash stability and (strict) core stability. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Computational Complexity Theory/Cryptology | |||||||
| Dokument erstellt am: | 17.03.2016 | |||||||
| Dateien geändert am: | 17.03.2016 | |||||||
| Promotionsantrag am: | 24.09.2015 | |||||||
| Datum der Promotion: | 12.01.2016 |
