Dokument: A Computational Complexity Study of Various Types of Electoral Control, Cloning, and Bribery
| Titel: | A Computational Complexity Study of Various Types of Electoral Control, Cloning, and Bribery | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=57532 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20210927-112639-9 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Neveling, Marc [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Prof. Dr. Rothe, Jörg [Gutachter] Jun.-Prof. Dr. Baumeister, Dorothea [Gutachter] [im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen] | |||||||
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
| Beschreibung: | This thesis deals with computational social choice which combines computational complexity theory,
one of the most important areas of theoretical computer science, with social choice theory which is highly relevant to economists, politicians, and other figures involved in decision-making processes. Although being a fairly young research field, springing to life in the early 1990s, computational social choice has established itself as one of the central pillars of artificial intelligence and multi-agent systems research. The central objects of interest for computational social choice are elections, which model decisionmaking processes where preferences of different agents or voters over candidates have to be aggregated into a final decision, and voting rules, which specify methods of how to aggregate those preferences. Naturally, all parties involved in an election, e.g., the agents, the organizing chair or even an outside agent, might have an interest to influence the outcome of an election. So-called election tampering attempts take many different forms: The agents may submit insincere preferences (i.e., strategic voting or election manipulation), the organizing chair might alter the structure of the election (i.e., electoral control) or an outside agent might want to bribe agents to change their votes to her liking (i.e., bribery). In this thesis we investigate, from a computational complexity perspective, to what degree elections evaluated by certain voting rules can be influenced by those types of election tampering attempts. Firstly, we study electoral control for the Borda Count which is one of the oldest and most important voting rules. We consider different types of electoral control such as adding or deleting candidates or voters and in particular electoral control by partitioning the candidates or voters into two groups. Furthermore, we consider so-called online electoral control in which candidates or voters appear one after another in the election and the chair may decide only in the moment of appearance to exert some control action. We find that Borda is rather resistant against electoral control by proving NP-hardness of several control problems. Secondly, we study replacement control which is a special kind of electoral control in which candidates or voters that are removed from the election need to be replaced by, as of yet, unregistered candidates or voters. We find that the complexity of replacement control problems usually follows the complexity of the corresponding classical control problems. Furthermore, we fill gaps in the literature regarding the complexity of the classical electoral control problems regarding adding or deleting candidates or voters. Thirdly, we consider multiwinner elections in which we seek to elect a fixed-sized set of candidates, a committee, instead of single candidates. We devise a model and define several decision problems to model electoral control by cloning of candidates. A candidate is cloned by adding a new candidate to the election that is very similar to the original candidate. We study the introduced model for cloning candidates in multiwinner elections for several popular multiwinner voting rules and find a wide range of complexity results. The last contribution of this thesis deals with shift bribery, which is a special kind of bribery in which only one special candidate may be moved forwards or backwards in the voters’ preferences. We study shift bribery for iterative voting rules that decide the outcome of an election in several rounds. We find that iterative voting rules are generally very resistant to shift bribery. In contrast to non-iterative voting rules, for which several examples of vulnerability against shift bribery can be found in the literature, shift bribery is NP-hard for all of our considered iterative voting rules. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Computational Complexity Theory/Cryptology | |||||||
| Dokument erstellt am: | 27.09.2021 | |||||||
| Dateien geändert am: | 27.09.2021 | |||||||
| Promotionsantrag am: | 09.06.2021 | |||||||
| Datum der Promotion: | 20.09.2021 |
