TY - GEN A1 - Kötzing, Timo A1 - Lagodzinski, Gregor J. A. A1 - Lengler, Johannes A1 - Melnichenko, Anna T1 - Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming T2 - Parallel Problem Solving from Nature – PPSN XV N2 - For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts). Second, the role and realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had a surprisingly little share in this work. We analyze a simple crossover operator in combination with local search, where a preference for small solutions minimizes bloat (lexicographic parsimony pressure); the resulting algorithm is denoted Concatenation Crossover GP. For this purpose three variants of the wellstudied Majority test function with large plateaus are considered. We show that the Concatenation Crossover GP can efficiently optimize these test functions, while local search cannot be efficient for all three variants independent of employing bloat control. Y1 - 2018 SN - 978-3-319-99259-4 SN - 978-3-319-99258-7 U6 - https://doi.org/10.1007/978-3-319-99259-4_4 SN - 0302-9743 SN - 1611-3349 VL - 11102 SP - 42 EP - 54 PB - Springer CY - Cham ER - TY - GEN A1 - Bilo, Davide A1 - Friedrich, Tobias A1 - Lenzner, Pascal A1 - Melnichenko, Anna T1 - Geometric Network Creation Games T2 - SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures N2 - Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design. KW - Network creation games KW - edge-weighted networks KW - price of anarchy KW - Nash equilibrium KW - game dynamics KW - computational hardness Y1 - 2019 SN - 978-1-4503-6184-2 U6 - https://doi.org/10.1145/3323165.3323199 SP - 323 EP - 332 PB - Association for Computing Machinery CY - New York ER - TY - JOUR A1 - Kötzing, Timo A1 - Lagodzinski, Gregor J. A. A1 - Lengler, Johannes A1 - Melnichenko, Anna T1 - Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming JF - Theoretical computer science N2 - For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation: the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts); and also the role and the realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had surprisingly little share in this work.
We analyze a simple crossover operator in combination with randomized local search, where a preference for small solutions minimizes bloat (lexicographic parsimony pressure); we denote the resulting algorithm Concatenation Crossover GP. We consider three variants of the well-studied MAJORITY test function, adding large plateaus in different ways to the fitness landscape and thus giving a test bed for analyzing the interplay of variation operators and bloat control mechanisms in a setting with local optima. We show that the Concatenation Crossover GP can efficiently optimize these test functions, while local search cannot be efficient for all three variants independent of employing bloat control. (C) 2019 Elsevier B.V. All rights reserved. KW - genetic programming KW - mutation KW - theory KW - run time analysis Y1 - 2020 U6 - https://doi.org/10.1016/j.tcs.2019.11.036 SN - 0304-3975 VL - 816 SP - 96 EP - 113 PB - Elsevier CY - Amsterdam ER - TY - THES A1 - Melnichenko, Anna T1 - Selfish Creation of Realistic Networks N2 - 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 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. N2 - 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 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. T2 - Spieltheoretische Erzeugung von realistischen Netzwerken KW - Algorithmic Game Theory KW - Network Creation Game KW - Price of Anarchy KW - Nash Equilibrium KW - Game Dynamics KW - Computational Hardness KW - Algorithmische Spieltheorie KW - Network Creation Game KW - Preis der Anarchie KW - Spieldynamik KW - Komplexität der Berechnung Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-548141 ER -