This dissertation focuses on robust coalition formation between selfish agents in a dynamic environment where contracts are unenforceable. Previous research on this topic has covered each different aspect of this problem, but no research successfully addresses these factors in combination. Therefore, a novel approach is required. This dissertation accordingly has three major goals: to develop a theoretical framework that describes how selfish agents should select jobs and partners in a dynamic, contractless environment, to test a strategy based on that framework against existing heuristics in a simulated environment, and to create a learning agent capable of optimally adjusting its coalition formation strategy based on the level of dynamic change found in its environment. Experimental results demonstrate that the Expected Utility (EU) strategy based on the developed theoretical framework performs better than strategies using heuristics to select jobs and partners, and strategies which simulate a centralized “manager”. Future work in this area includes altering the EU strategy from an anytime strategy to a hill-climbing one, as well as further game theoretic explorations of the interactions between different strategies. / text

Untersuchungsgegenstand dieser Arbeit ist ein spieltheoretisches Modell für die dezentrale Erzeugung von Netzwerken durch eigennützige Agenten. Diese Akteure verfolgen das Ziel, ein zusammenhängendes Netzwerk aufzubauen, welches ihre individuelle Verbindungsqualität maximiert. Direktverbindungen im Netzwerk haben Kosten, weshalb die Agenten ihre Ausgaben für das Erstellen von Direktverbindungen und die damit erzielten Kommunikationskosten ausbalancieren müssen. Dieses Modell wurde vor einem Jahrzehnt von Fabrikant, Luthra, Maneva, Papadimitriou und Shenker eingeführt, um reale Netzwerke, welche aus der Interaktion von eigenützigen Parteien entstanden sind, zu verstehen. Zu solchen Netzwerken zählen das Internet und auch soziale Netzwerke. Die vorliegende Arbeit trägt zu diesem Forschungsvorhaben bei, indem die sogenannten Network Creation Games aus drei Perspektiven betrachtet werden. Die erste Sichtweise ist die Approximationsperspektive. Es wird untersucht, welche Netzwerke von sehr einfachen, in ihrer Berechnungsstärke eingeschränkten Agenten erzeugt werden und wie diese im Vergleich mit Netzwerken von Agenten, die beliebige Berechnungsstärke haben, abschneiden. Als zweite Sichtweise wird die Dynamikperspektive betrachtet. Dazu werden sequentielle Versionen des Modells definiert und anhand dieser wird explizit der Prozess der Netzwerkerzeugung untersucht. Die Hauptfragestellung ist, ob unter der natürlichen Annahme, dass Agenten stets ihre Situation verbessern wollen, der Prozess zu einem Gleichgewicht konvergiert und, falls dem so ist, wie dieser Prozess beschleunigt werden kann. Die Abhandlung wird mit der dritten Sichtweise, der Strukturperspektive, abgerundet. Es werden eine Vielfalt neuer Struktureigenschaften für verschiedene Gleichgewichtskonzepte bewiesen und neue Werkzeuge, die bei der Analyse von Gleichgewichtsnetzwerken mit hohen Direktverbindungskosten hilfreich sind, vorgestellt. / The subject of study in this thesis is a game-theoretic model for decentralized network creation by selfish agents. These agents aim to create a connected network among themselves which maximizes their individual connection quality. Links in the network are costly and therefore agents try to find a trade-off between their cost spent on creating edges and their cost incurred by communicating within the network. This model was proposed a decade ago by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker with the goal of understanding real networks which emerge from the interaction of selfish entities without explicit central coordination, e.g. the Internet or social networks. We contribute to this research endeavor in many ways by considering these so-called Network Creation Games from three perspectives. Our first point of view on these games is the approximation perspective. We analyze which networks are created by very simple computationally bounded selfish agents and how these networks compare to networks built by agents having unlimited computational resources. The second point of view is the dynamics perspective. We turn the model into a sequential version and focus on the process of selfish network creation. For this, we investigate whether natural dynamics like best response dynamics are guaranteed to converge to an equilibrium of the game and if so, how this convergence process may be sped up. We complete the treatment of Network Creation Games with our third point of view: the structure perspective. We provide new structural insights for several equilibrium concepts and introduce new tools which shed light on the structure of equilibrium networks for high edge-cost.