Dokument: From Elections to Tournaments: A Study of the Computational Complexity of Bribery, Design, and Prediction Problems in Voting and Sports
| Titel: | From Elections to Tournaments: A Study of the Computational Complexity of Bribery, Design, and Prediction Problems in Voting and Sports | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=61931 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20230210-075202-5 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Deutsch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Hogrebe, Tobias Alexander [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Jun.-Prof. Dr. Baumeister, Dorothea [Gutachter] [im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen] Dr. Grandi, Umberto [Gutachter] Prof. Dr. Grossi, Davide [Gutachter] | |||||||
| Beschreibung: | This thesis is concerned with the study of the computational complexity of problems related to elections and sport tournaments from the field of computational social choice. The latter field, which is one of the youngest areas of theoretical computer science, primarily builds on the field of computational complexity theory, which studies the difficulty of solving problems from an algorithmic perspective, and the field of social choice theory, which studies decision-making processes from an axiomatic perspective. At its heart lies the study of the computational complexity of problems related to decision-making processes such as elections, tournaments, resource allocation, judgment aggregation, and matching. Despite its relatively young age, computational social choice is considered as a central and very active field of artificial intelligence and multi-agent systems research, attracting computer scientists, economists, and sociologists alike.
A key aspect that accompanies us through this thesis is the concept of uncertainty in elections and tournaments in relation to computational complexity. This includes, for example, uncertainty about the preferences of voters, about the voting rule, and about the outcome of the remaining matches in a tournament. In more detail, we focus on the following topics. We start by studying the computational complexity of decision problems concerning bribery and the evaluation of the robustness of election outcomes. We apply concepts from classical decision complexity and show that the problems can be solved in polynomial time for certain combinations of voting rules and types of functions measuring the strength of changes or uncertainty in the votes, while for other cases they are NP-complete and thus unlikely to have polynomial-time solutions. Afterwards, we study the computational complexity of the problem of designing scoring systems for elections and competitions with the goal of guaranteeing the victory of a desired candidate or checking the robustness of a candidate’s victory with respect to the system used. Besides various results regarding the classical decision complexity, in terms of membership in P and NP-completeness, we further differentiate the complexity with respect to different parameterizations and show FPT and W[2]-hardness results and conclude with experiments on real-world data. Regarding elections with probabilistically distributed preferences, we study the function complexity of determining the winning probabilities of candidates for different combinations of voting rules, distribution models, tie-breaking procedures, and parameterizations using concepts from counting complexity. We show membership in FP for some cases, while showing #P-hardness for other cases. We then move to roundrobin tournaments and study the function complexity of calculating the probability that a given team ends up as the champion under the assumption that we are in the course of a tournament, whereby some of the matches have already been played while others remain to be played. Again, we apply concepts of counting complexity, examine different parameterizations, and show memberships in FP, #P-hardness, and FPT results. In addition, we perform experiments on real-world data and synthetic data and, motivated by the empirical results, study the average-case complexity of the problem and show the expected polynomial time of our FPT algorithm for certain distributions. Finally, we switch from studying the complexity of problems whose instances model uncertainties to studying the complexity of problems under the assumption of uncertainties about the instances and discuss our proposal of applying the concept of smoothed analysis in the field of computational social choice. | |||||||
| 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: | 10.02.2023 | |||||||
| Dateien geändert am: | 10.02.2023 | |||||||
| Promotionsantrag am: | 17.05.2022 | |||||||
| Datum der Promotion: | 09.12.2022 |
