Anna Melnichenko

• Complex networks like the Internet or social networks are fundamental parts of our everyday lives. It is essential to understand their structural properties and how these networks are formed. A game-theoretic approach to network design problems has become of high interest in the last decades. The reason is that many real-world networks are the outcomes of decentralized strategic behavior of independent agents without central coordination. Fabrikant, Luthra, Maneva, Papadimitriou, and Schenker proposed a game-theoretic model aiming to explain the formation of the Internet-like networks. In this model, called the Network Creation Game, agents are associated with nodes of a network. Each agent seeks to maximize her centrality by establishing costly connections to other agents. The model is relatively simple but shows a high potential in modeling complex real-world networks. In this thesis, we contribute to the line of research on variants of the Network Creation Games. Inspired by real-world networks, we propose and analyze several novelComplex networks like the Internet or social networks are fundamental parts of our everyday lives. It is essential to understand their structural properties and how these networks are formed. A game-theoretic approach to network design problems has become of high interest in the last decades. The reason is that many real-world networks are the outcomes of decentralized strategic behavior of independent agents without central coordination. Fabrikant, Luthra, Maneva, Papadimitriou, and Schenker proposed a game-theoretic model aiming to explain the formation of the Internet-like networks. In this model, called the Network Creation Game, agents are associated with nodes of a network. Each agent seeks to maximize her centrality by establishing costly connections to other agents. The model is relatively simple but shows a high potential in modeling complex real-world networks. In this thesis, we contribute to the line of research on variants of the Network Creation Games. Inspired by real-world networks, we propose and analyze several novel network creation models. We aim to understand the impact of certain realistic modeling assumptions on the structure of the created networks and the involved agents’ behavior. The first natural additional objective that we consider is the network’s robustness. We consider a game where the agents seek to maximize their centrality and, at the same time, the stability of the created network against random edge failure. Our second point of interest is a model that incorporates an underlying geometry. We consider a network creation model where the agents correspond to points in some underlying space and where edge lengths are equal to the distances between the endpoints in that space. The geometric setting captures many physical real-world networks like transport networks and fiber-optic communication networks. We focus on the formation of social networks and consider two models that incorporate particular realistic behavior observed in real-world networks. In the first model, we embed the anti-preferential attachment link formation. Namely, we assume that the cost of the connection is proportional to the popularity of the targeted agent. Our second model is based on the observation that the probability of two persons to connect is inversely proportional to the length of their shortest chain of mutual acquaintances. For each of the four models above, we provide a complete game-theoretical analysis. In particular, we focus on distinctive structural properties of the equilibria, the hardness of computing a best response, the quality of equilibria in comparison to the centrally designed socially optimal networks. We also analyze the game dynamics, i.e., the process of sequential strategic improvements by the agents, and analyze the convergence to an equilibrium state and its properties.…
• Komplexe Netzwerke, wie das Internet oder soziale Netzwerke, sind fundamentale Bestandteile unseres Alltags. Deshalb ist es wichtig, ihre strukturellen Eigenschaften zu verstehen und zu wissen, wie sie gebildet werden. Um dies zu erreichen, wurden in den letzten Jahrzehnten spieltheoretische Ansätze für Netzwerkdesignprobleme populär. Der Grund dafür ist, dass viele reale Netzwerke das Ergebnis von dezentralem strategischem Verhalten unabhängiger Agenten ohne zentrale Koordination sind. Fabrikant, Luthra, Maneva, Papadimitriou und Schenker haben ein solches spieltheoretisches Modell vorgeschlagen, um die Entstehung von internetähnlichen Netzwerken zu erklären. In diesem Modell, dem sogenannten Network Creation Game, repräsentieren die Agenten die Knoten eines Netzwerks. Jeder Agent versucht, durch den Kauf von Verbindungen zu anderen Agenten seine Zentralität im erzeugten Netzwerk zu maximieren. Dieses Modell ist relativ einfach, aber es hat ein großes Potenzial, reale Netzwerke modellieren zu können. In der vorliegenden ArbeitKomplexe Netzwerke, wie das Internet oder soziale Netzwerke, sind fundamentale Bestandteile unseres Alltags. Deshalb ist es wichtig, ihre strukturellen Eigenschaften zu verstehen und zu wissen, wie sie gebildet werden. Um dies zu erreichen, wurden in den letzten Jahrzehnten spieltheoretische Ansätze für Netzwerkdesignprobleme populär. Der Grund dafür ist, dass viele reale Netzwerke das Ergebnis von dezentralem strategischem Verhalten unabhängiger Agenten ohne zentrale Koordination sind. Fabrikant, Luthra, Maneva, Papadimitriou und Schenker haben ein solches spieltheoretisches Modell vorgeschlagen, um die Entstehung von internetähnlichen Netzwerken zu erklären. In diesem Modell, dem sogenannten Network Creation Game, repräsentieren die Agenten die Knoten eines Netzwerks. Jeder Agent versucht, durch den Kauf von Verbindungen zu anderen Agenten seine Zentralität im erzeugten Netzwerk zu maximieren. Dieses Modell ist relativ einfach, aber es hat ein großes Potenzial, reale Netzwerke modellieren zu können. In der vorliegenden Arbeit tragen wir zur aktuellen Forschungsrichtung, die sich der Untersuchung von Varianten der Network Creation Games widmet, bei. Inspiriert von realen Netzwerken, schlagen wir verschiedene neuartige Netzwerkbildungsmodelle vor und analysieren diese. Wir wollen hierbei die Auswirkungen bestimmter realistischer Modellierungsannahmen auf die Struktur der erstellten Netzwerke und das Verhalten der beteiligten Agenten verstehen. Die erste natürliche zusätzliche Modellierungsannahme, die wir betrachten, ist ein Fokus auf die Robustheit des erzeugten Netzwerks. In diesem Modell haben die Agenten das Ziel, ihre Zentralität zu maximieren und gleichzeitig das erstellte Netzwerk robust gegenüber zufällige Verbindungsausfälle zu machen. Das zweite neue Modell, das wir hier betrachten, bezieht eine zu Grunde liegende Geometrie mit ein. Hierbei entspricht jeder Agent einem Punkt in einem gegebenen Raum und die Länge einer Netzwerkverbindung entspricht der Distanz zwischen den jeweiligen Endpunkten in diesem Raum. Diese geometrische Variante erlaubt die Modellierung vieler realer physischer Netzwerke, wie z.B. Transportnetzwerke und Glasfaserkommunikationsnetzwerke. Des Weiteren fokussieren wir uns auf die Bildung von sozialen Netzwerken und betrachten zwei Modelle, die ein bestimmtes realistisches Verhalten einbeziehen, das in realen sozialen Netzwerken beobachtet werden kann. Das erste Modell basiert auf einer anti-präferentiellen Kantenerzeugung. Dabei nehmen wir an, dass die Kosten einer Verbindung proportional zur Popularität des Agenten am anderen Endpunkt sind. Das zweite betrachtete Modell basiert auf der Beobachtung, dass die Wahrscheinlichkeit, dass zwei Personen verbunden sind, proportional zur Länge ihrer kürzesten Kette von gegenseitigen Bekanntschaften ist. Für jedes der vier oben genannten Modelle liefern wir eine komplette spieltheoretische Analyse. Insbesondere fokussieren wir uns auf charakteristische strukturelle Eigenschaften der spieltheoretischen Gleichgewichte, die Komplexität der Berechnung einer optimalen Strategie und die Qualität der Gleichgewichte im Vergleich zu den zentral entworfenen sozial optimalen Netzwerken. Außerdem analysieren wir die Spieldynamik, d.h. den Prozess von sequentiellen verbessernden Strategieänderungen der Agenten. Dabei untersuchen wir die Konvergenz zu einem Gleichgewichtszustand und die Eigenschaften solcher Konvergenzprozesse.…