Dokument: A User's Theory - How to Model Agents of Online Debates
| Titel: | A User's Theory - How to Model Agents of Online Debates | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=50045 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20190702-100802-3 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Schadrack, Hilmar [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Jun.-Prof. Dr. Baumeister, Dorothea [Gutachter] [im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen] Prof. Dr. Rothe, Jörg [Gutachter] | |||||||
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
| Beschreibung: | This thesis deals with hedonic games and abstract argumentation, both lively research fields that belong to the areas of multiagent systems and artificial intelligence. This work includes research on hedonic games in two ways. First, we study the computational complexity of a special case for hedonic games in which agents only express sets of friends and enemies, but not total rankings; we narrow existing gaps in complexity regarding the existence of the strict core in these games with the help of closely related graph problems. Second, we introduce a new model for hedonic games that allows for a compact, yet quite expressive representation. Sadly, our model suffers from a problem of incomparable coalitions. We address this issue on the one hand with the help of possibility and necessity notions, and on the other through means of comparability functions that work similar to the Borda-scoring vectors from social choice theory.
In detail, we will show that in the first case with enemy-oriented preferences, it is at least DP-hard to decide whether the strict core of a given hedonic game is nonempty, and that its complexity cannot rise above the second level of the boolean hierarchy. The same holds for the encountered graph problem of deciding whether an undirected graph contains a wonderfully stable partition. For the second case, we will provide a comprehensive analysis of the model's properties, as well as one possibility of how to extend the resulting incomplete preference over coalitions for each player in form of the polarized responsive extension principle. Our analysis also includes a classification of the computational complexity of the verification and existence problems for several stability concepts including the (strict) core, Nash stability, perfectness, Pareto optimality and more. This includes hardness and completeness results for NP and the second level of the polynomial hierarchy, but also feasibility results in both cases, i.e., for the notions of possibility and necessity, as well as for Borda-induced hedonic games. Regarding abstract argumentation, we focus on an expansion of the basic model such that we can deal with situations in which complete information over all given arguments and their interactions is not given beforehand. That is, we introduce another set of arguments and attacks for which it is not clear from the start whether they will be part of the debate or not. We then use notions of possibility and necessity to deal with this high degree of uncertainty and analyze this model in terms of computational complexity. More specifically, we will show that the verification problem for argumentation frameworks can be extended to fit to the new model, and that its computational complexity can rise up to completeness for the second level of the polynomial hierarchy. However, this increase only happens in situations in which we have to deal with alternating quantifiers. In all other cases we can find shortcuts that allow for a faster solution to the problem. Both parts of this work illuminate different views on the behavior of agents. When focusing on an abstract level of indirect interaction as in hedonic games, we can concentrate more on the bigger picture instead of the overwhelming density of argumentative approaches. However, on the side of abstract argumentation, we directly use this comprehensive information regarding a specific argumentation process to directly elicit a solution, while abstracting from external influences. Both views are needed to correctly and completely model all possible actions of any kind of agent. This thesis takes another step on this agenda. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik | |||||||
| Dokument erstellt am: | 02.07.2019 | |||||||
| Dateien geändert am: | 02.07.2019 | |||||||
| Promotionsantrag am: | 05.02.2019 | |||||||
| Datum der Promotion: | 04.06.2019 |
