Dokument: Computational Analysis of Electoral Control in Single- and Multiwinner Elections
| Titel: | Computational Analysis of Electoral Control in Single- and Multiwinner Elections | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=71725 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20260105-125522-9 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Zorn, Roman [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Prof. Dr. Rothe, Jörg-Matthias [Gutachter] Prof. Dr. Wanke, Egon [Gutachter] | |||||||
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
| Beschreibung: | In this thesis we study the computational complexity of several decision problems in the area
of electoral control. Electoral control is a part of computational voting theory which in turn belongs to the research area of computational social choice. In this model, a group of voters expresses their preferences over a set of candidates, and a specified voting rule is used to determine the winners of this election. In electoral control, an agent – called the chair – can influence the structure of a given election by, for example, removing or adding candidates. The chair’s goal is either to help a particular candidate win or to prevent a particular candidate from winning. Since we want to prevent these kinds of malicious actions, we herein study the computational complexity of decision problems that model them. In simple terms, the higher the complexity of such a problem, the harder it is for the chair to compute which candidates need to be added (or removed) to achieve their objective. Therefore, high complexity can be viewed as a desirable feature when selecting a voting rule. A special focus of this thesis is the control action of replacing candidates or voters. This type of control action has not been studied as much as others in the literature before. When replacing, the chair may simultaneously add and remove voters or candidates, but the number added must equal the number removed, so that the election’s overall size remains unchanged. This might be used in practice to conceal the chair’s tampering with the election. We therefore study the complexity of control by replacing for various voting rules in this thesis. Another important focus of our work is multiwinner elections. In this model, the winner of the election is not a single candidate but a set of candidates, called a committee. In this thesis we show the complexity of control by replacing for two widely used multiwinner voting rules. We also investigate multiwinner voting rules in the context of the complexity of their control problems concerning the cloning of candidates. When cloning candidates, the chair can create new candidates that are so similar to already existing ones that each voter ranks these candidates as a contiguous block in their preference order. We study this model in both an optimistic and a pessimistic setting and under three different cost models. In the most general model, the cost of cloning a candidate varies from clone to clone and from candidate to candidate; in the most specific model, cloning is entirely free. | |||||||
| 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: | 05.01.2026 | |||||||
| Dateien geändert am: | 05.01.2026 | |||||||
| Promotionsantrag am: | 12.08.2025 | |||||||
| Datum der Promotion: | 15.12.2025 |
