Dokument: An Axiomatic and Computational Analysis of Altruism, Fairness, and Stability in Coalition Formation Games

Titel:	An Axiomatic and Computational Analysis of Altruism, Fairness, and Stability in Coalition Formation Games
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=60897
URN (NBN):	urn:nbn:de:hbz:061-20221017-105710-9
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Kerkmann, Anna Maria [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 811,9 KB in einer Datei [ZIP-Datei erzeugen] Dateien vom 11.10.2022 / geändert 11.10.2022
Beitragende:	Prof. Dr. Rothe, Jörg-Matthias [Gutachter] Jun.-Prof. Dr. Bredereck, Robert [Gutachter] Prof. Dr. Hoefer, Martin [Gutachter]
Stichwörter:	game theory, coalition formation, hedonic games
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:	Diese Arbeit beschäftigt sich mit Koalitionsbildungsspielen, welche zum Forschungsbereich der kooperativen Spieltheorie gehören. Bei diesen Spielen geht es darum, wie sich Spieler auf Grundlage ihrer individuellen Präferenzen in Gruppen, auch Koalitionen genannt, aufteilen. Bei unseren Untersuchungen konzentrieren wir uns größtenteils auf hedonische Koalitionsbildungsspiele, kurz hedonische Spiele, bei welchen vorausgesetzt wird, dass die Präferenzen der Spieler nur von ihren eigenen Koalitionen abhängen. Ein zentrales Thema in Bezug auf diese Spiele ist die Suche nach sinnvollen Formaten zur Abgabe der Präferenzen. Diese Formate sollten einfach zu erheben, möglichst ausdrucksstark und zugleich kompakt darstellbar sein. In der einschlägigen Literatur wurden bereits einige solcher Formate vorgestellt, die auch wir in dieser Arbeit behandeln werden. Ein zweiter wichtiger Punkt bei der Erforschung von hedonischen Spielen ist die Untersuchung von Stabilität, Fairness und Optimalität. Klassische Stabilitätskonzepte behandeln beispielsweise die Frage, ob einzelne Spieler oder Gruppen von Spielern einen Anreiz haben, von ihren Koalitionen abzuweichen. Zu den bekanntesten solcher Konzepte gehören Nash-Stabilität und Kernstabilität. Auf Grundlage des aktuellen Stands der Literatur führen wir in dieser Arbeit neue Modelle für (hedonische) Koalitionsbildungsspiele ein und untersuchen diese im Hinblick auf axiomatische Eigenschaften, Stabilität, Fairness und Optimalität. Dabei spielen insbesondere Untersuchungen der Berechnungskomplexität eine wichtige Rolle. Zuerst stellen wir verschiedene Modelle für Altruismus in Koalitionsbildungsspielen vor. Wir konzentrieren uns dabei zunächst auf den Kontext von hedonischen Spielen und erweitern die Modelle anschließend auf allgemeinere Koalitionsbildungsspiele, bei denen eine weitreichendere Form des Altruismus' möglich ist. Wir untersuchen unsere Modelle axiomatisch und vergleichen diese dabei untereinander und mit anderen Modellen. Zudem analysieren wir die Entscheidungsprobleme, die sich bei der Betrachtung klassischer Stabilitätskonzepte im Kontext von altruistischen Spielen ergeben, in Hinblick auf ihre Berechnungskomplexität. Anschließend definieren wir drei schwellwertbasierte Fairnessbegriffe für hedonische Spiele. Diese werden in den Kontext einschlägiger Stabilitäts- und Fairnesskonzepte eingeordnet und im Hinblick auf ihre Berechnungskomplexität erforscht. Außerdem untersuchen wir den Einfluss, den unsere Fairnesskonzepte auf die soziale Wohlfahrt haben. Schließlich führen wir ein weiteres Präferenzformat ein, bei dem die Spieler zwischen Freunden, neutralen Spielern und Feinden unterscheiden. Sie geben dementsprechend eine dreigeteilte schwache Ordnung ab. Da die Präferenzen, welche sich aus diesen Ordnungen ableiten lassen, nicht vollständig sein müssen, unterscheiden wir in den entstehenden Spielen zwischen möglicher und notwendiger Stabilität. Auch hier führen wir eine Komplexitätsanalyse der Probleme durch, die sich bezüglich bekannter Stabilitätskonzepte ergeben. This thesis deals with coalition formation games, which belong to the research area of cooperative game theory. In these games, players divide into groups, also called coalitions, based on their individual preferences. In our research, we mainly focus on hedonic coalition formation games, hedonic games for short, in which players' preferences are assumed to depend only on the coalitions containing themselves. A central problem in hedonic games research is finding reasonable formats for the elicitation of preferences. These preference representations should be easy to elicit, reasonably expressive, and succinct. Many such formats have already been presented in related literature, some of which we will also discuss in this thesis. A second central point in research concerning hedonic games is the investigation of stability, fairness, and optimality. For instance, common stability concepts deal with the question of whether individual players or groups of players might have an incentive to deviate from their current coalitions. Among those notions are, for example, Nash and core stability. Based on the current state of research, we introduce new models for (hedonic) coalition formation games and investigate them with respect to axiomatic properties, stability, fairness, and optimality. In particular, investigations of the computational complexity of the associated decision problems play an important role. We start with introducing several models for altruism in coalition formation games. First, we focus on the context of hedonic games and then extend the models to more general coalition formation games, where a broader form of altruism is possible. We conduct an axiomatic analysis of our models and compare them to related models and to each other. In addition, we study the problems, that arise when considering classical stability concepts in the context of altruistic coalition formation games, with respect to their computational complexity. Subsequently, we define three threshold-based fairness notions for hedonic games. These notions are considered local fairness notions in the sense that the agents only have to inspect their own coalitions to decide whether a coalition structure is fair to them. We study the relations of these notions to other common stability and fairness concepts and examine them with respect to their computational complexity. Furthermore, we investigate the price of local fairness, i.e., the impact that our fairness concepts have on the social welfare. Finally, we introduce another preference format in which players distinguish between friends, neutral players, and enemies. Accordingly, they cast their preferences by submitting a weak rankings that is separated by two thresholds. Since the preferences that can be derived from these rankings are not necessarily complete, we distinguish between possible and necessary stability in the resulting games. Again, we perform a computational complexity analysis of the problems that arise with respect to common stability concepts.
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:	17.10.2022
Dateien geändert am:	17.10.2022
Promotionsantrag am:	10.05.2022
Datum der Promotion:	28.09.2022