{'fraction_non_alphanumeric': 0.015518311607697082, 'fraction_numerical': 0.0006207324643078833, 'mean_word_length': 5.05827067669173, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On selfish network creation

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 [FLM+03] 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. If the individual connection quality of an agent is measured with the sum of shortest path distances to all other agents, then we find that simple agents create networks which are remarkably close to networks created by supernatural agents. On the other hand, if the individual connection quality of an agent is measured with the maximum over the shortest path distances to all other agents, then we get the contrasting result that this only holds for tree networks and that other created networks may be very far away from the optimum. 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. The results are diverse: If agents are restricted to performing edge-swaps then we have guaranteed and very fast convergence if the initial network is a tree. On the other hand, if the initial network is not a tree or if agents may perform richer strategy-changes, then we can show that this process may never converge. We contrast these mostly negative theoretical results with a careful empirical study. There, we observe reliable and surprisingly fast convergence towards equilibrium networks. Thus, despite our negative results, such egoistic self stabilization processes may be a promising practical approach for finding equilibrium networks. We complete the treatment of Network Creation Games with our third point of view: the structure perspective. The individual quality of a selfishly created network for the agents is determined by its structure. Thus, a rigorous understanding of the shape of equilibrium networks seems necessary to understand the deterioration in quality due to the selfishness of the agents the so-called Price of Anarchy. 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.