Publications of Dr. Anna Melnichenko

2024 [ nach oben ]

Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna Geometric Network Creation GamesSIAM Journal on Discrete Mathematics 2024: 277–315
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
Network creation games are a well-known approach for explaining and analyzing the structure, quality, and dynamics of real-world networks that evolved via the interaction of selfish agents without a central authority. In these games selfish agents corresponding to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games 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 depend 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. [Proceedings of PODC ’03, ACM, 2003, pp. 347–351] 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 nonconstant bound on the price of anarchy for the metric version and a slightly weaker upper bound for the nonmetric 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 the classical network design problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.
@article{bilo2023geometric, abstract = {Network creation games are a well-known approach for explaining and analyzing the structure, quality, and dynamics of real-world networks that evolved via the interaction of selfish agents without a central authority. In these games selfish agents corresponding to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games 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 depend 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. [Proceedings of PODC ’03, ACM, 2003, pp. 347–351] 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 nonconstant bound on the price of anarchy for the metric version and a slightly weaker upper bound for the nonmetric 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 the classical network design problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.}, author = {Bilò, Davide and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {annamelnichenko pascallenzner sidma tobiasfriedrich year2024}, number = 1, pages = {277-315}, title = {Geometric Network Creation Games}, volume = 38, year = 2024 }

2023 [ nach oben ]

Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna Social Distancing Network CreationAlgorithmica 2023
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al. (in: PODC 2003, pp 347–351, 2003. https://doi.org/10.1145/872035.872088), where agents aim at being as central as possible in the created network. We look at two variants of network creation governed by social distancing. Firstly, a variant without connection restrictions, where we characterize optimal and equilibrium networks, and derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant allows connection restrictions. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that under social distancing the agents’ selfishness has a strong impact on the quality of the equilibria.
@article{friedrich2023social, abstract = {During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al. (in: PODC 2003, pp 347–351, 2003. https://doi.org/10.1145/872035.872088), where agents aim at being as central as possible in the created network. We look at two variants of network creation governed by social distancing. Firstly, a variant without connection restrictions, where we characterize optimal and equilibrium networks, and derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant allows connection restrictions. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that under social distancing the agents’ selfishness has a strong impact on the quality of the equilibria.}, author = {Friedrich, Tobias and Gawendowicz, Hans and Lenzner, Pascal and Melnichenko, Anna}, journal = {Algorithmica}, keywords = {algorithmica annamelnichenko hansgawendowicz pascallenzner tobiasfriedrich year2023}, title = {Social Distancing Network Creation}, year = 2023 }

2022 [ nach oben ]

Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna Social Distancing Network CreationInternational Colloquium on Automata, Languages and Programming (ICALP) 2022: 62:1–62:21
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al.~[PODC 2003] where agents aim at being as central as possible in the created network. Thus, our work is in-line with studies that compare minimization problems with their maximization versions. We look at two variants of network creation governed by social distancing. In the first variant, there are no restrictions on the connections being formed. We characterize optimal and equilibrium networks, and we derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant is the model's generalization that allows restrictions on the connections that can be formed. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that, compared the well-studied inverse models, under social distancing the agents' selfish behavior has a significantly stronger impact on the quality of the equilibria, i.e., allowing socially much worse stable states.
@inproceedings{friedrich2022social, abstract = {During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al. [PODC 2003] where agents aim at being as central as possible in the created network. Thus, our work is in-line with studies that compare minimization problems with their maximization versions. We look at two variants of network creation governed by social distancing. In the first variant, there are no restrictions on the connections being formed. We characterize optimal and equilibrium networks, and we derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant is the model's generalization that allows restrictions on the connections that can be formed. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that, compared the well-studied inverse models, under social distancing the agents' selfish behavior has a significantly stronger impact on the quality of the equilibria, i.e., allowing socially much worse stable states.}, author = {Friedrich, Tobias and Gawendowicz, Hans and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {annamelnichenko hansgawendowicz icalp pascallenzner tobiasfriedrich year2022}, pages = {62:1–62:21}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{{ü}}r Informatik}, title = {Social Distancing Network Creation}, volume = {LIPIcs:229}, year = 2022 }

Bullinger, Martin; Lenzner, Pascal; Melnichenko, Anna Network Creation with Homophilic AgentsInternational Joint Conference on Artificial Intelligence (IJCAI) 2022: 151–157
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Network Creation Games are an important framework for understanding the formation of real-world networks such as social networks. These games usually assume a set of indistinguishable agents strategically buying edges at a uniform price leading to a network among them. However, in real life, agents are heterogeneous and their relationships often display a bias towards similar agents, say of the same ethnic group. This homophilic behavior on the agent level can then lead to the emergent global phenomenon of social segregation. We initiate the study of Network Creation Games with multiple types of homophilic agents and non-uniform edge cost. Specifically, we introduce and compare two models, focusing on the perception of same-type and different-type neighboring agents, respectively. Despite their different initial conditions, both our theoretical and experimental analysis show that the resulting equilibrium networks are almost identical in the two models, indicating a robust structure of social networks under homophily. Moreover, we investigate the segregation strength of the formed networks and thereby offer new insights on understanding segregation.
@inproceedings{bullinger2022network, abstract = {Network Creation Games are an important framework for understanding the formation of real-world networks such as social networks. These games usually assume a set of indistinguishable agents strategically buying edges at a uniform price leading to a network among them. However, in real life, agents are heterogeneous and their relationships often display a bias towards similar agents, say of the same ethnic group. This homophilic behavior on the agent level can then lead to the emergent global phenomenon of social segregation. We initiate the study of Network Creation Games with multiple types of homophilic agents and non-uniform edge cost. Specifically, we introduce and compare two models, focusing on the perception of same-type and different-type neighboring agents, respectively. Despite their different initial conditions, both our theoretical and experimental analysis show that the resulting equilibrium networks are almost identical in the two models, indicating a robust structure of social networks under homophily. Moreover, we investigate the segregation strength of the formed networks and thereby offer new insights on understanding segregation.}, author = {Bullinger, Martin and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {annamelnichenko ijcai pascallenzner year2022}, pages = {151–157}, publisher = {ijcai.org}, title = {Network Creation with Homophilic Agents}, year = 2022 }

2021 [ nach oben ]

Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Lowski, Stefanie; Melnichenko, Anna Selfish Creation of Social NetworksConference on Artificial Intelligence (AAAI) 2021: 5185–5193
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Understanding real-world networks has been a core research endeavor throughout the last two decades. Network Creation Games are a promising approach for this from a game-theoretic perspective. In these games, selfish agents corresponding to nodes in a network strategically decide which links to form to optimize their centrality. Many versions have been introduced and analyzed, but none of them fits to modeling the evolution of social networks. In real-world social networks, connections are often established by recommendations from common acquaintances or by a chain of such recommendations. Thus establishing and maintaining a contact with a friend of a friend is easier than connecting to complete strangers. This explains the high clustering, i.e., the abundance of triangles, in real-world social networks. We propose and analyze a network creation model inspired by real-world social networks. Edges are formed in our model via bilateral consent of both endpoints and the cost for establishing and maintaining an edge is proportional to the distance of the endpoints before establishing the connection. We provide results for generic cost functions, which essentially only must be convex functions in the distance of the endpoints without the respective edge. For this broad class of cost functions, we provide many structural properties of equilibrium networks and prove (almost) tight bounds on the diameter, the Price of Anarchy and the Price of Stability. Moreover, as a proof-of-concept we show via experiments that the created equilibrium networks of our model indeed closely mimics real-world social networks. We observe degree distributions that seem to follow a power-law, high clustering, and low diameters. This can be seen as a promising first step towards game-theoretic network creation models that predict networks featuring all core real-world properties.
@inproceedings{bilo2021selfish, abstract = {Understanding real-world networks has been a core research endeavor throughout the last two decades. Network Creation Games are a promising approach for this from a game-theoretic perspective. In these games, selfish agents corresponding to nodes in a network strategically decide which links to form to optimize their centrality. Many versions have been introduced and analyzed, but none of them fits to modeling the evolution of social networks. In real-world social networks, connections are often established by recommendations from common acquaintances or by a chain of such recommendations. Thus establishing and maintaining a contact with a friend of a friend is easier than connecting to complete strangers. This explains the high clustering, i.e., the abundance of triangles, in real-world social networks. We propose and analyze a network creation model inspired by real-world social networks. Edges are formed in our model via bilateral consent of both endpoints and the cost for establishing and maintaining an edge is proportional to the distance of the endpoints before establishing the connection. We provide results for generic cost functions, which essentially only must be convex functions in the distance of the endpoints without the respective edge. For this broad class of cost functions, we provide many structural properties of equilibrium networks and prove (almost) tight bounds on the diameter, the Price of Anarchy and the Price of Stability. Moreover, as a proof-of-concept we show via experiments that the created equilibrium networks of our model indeed closely mimics real-world social networks. We observe degree distributions that seem to follow a power-law, high clustering, and low diameters. This can be seen as a promising first step towards game-theoretic network creation models that predict networks featuring all core real-world properties.}, author = {Bilò, Davide and Friedrich, Tobias and Lenzner, Pascal and Lowski, Stefanie and Melnichenko, Anna}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai annamelnichenko davidebilo pascallenzner stefanielowski tobiasfriedrich year2021}, pages = {5185-5193}, title = {Selfish Creation of Social Networks}, year = 2021 }

Friedemann, Wilhelm; Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna; Peters, Jannik; Stephan, Daniel; Vaichenker, Michael Efficiency and Stability in Euclidean Network DesignSymposium on Parallelism in Algorithms and Architectures (SPAA) 2021: 232–242
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Network Design problems typically ask for a minimum cost sub-network from a given host network. This classical point-of-view assumes a central authority enforcing the optimum solution. But how should networks be designed to cope with selfish agents that own parts of the network? In this setting, minimum cost networks may be very unstable in that agents will deviate from a proposed solution if this decreases their individual cost. Hence, designed networks should be both efficient in terms of total cost and stable in terms of the agents' willingness to accept the network. We study this novel type of Network Design problem by investigating the creation of \($(\beta,\gamma)$\)-networks, that are in \($\beta$\)-approximate Nash equilibrium and have a total cost of at most \($\gamma$\) times the optimal cost, for the recently proposed Euclidean Generalized Network Creation Game by Bilò et al.SPAA2019. There, \($n$\) agents corresponding to points in Euclidean space create costly edges among themselves to optimize their centrality in the created network. Our main result is a simple \($\mathcal{O(n^2)$\)-time algorithm that computes a \($(\beta,\beta)$\)-network with low \($\beta$\) for any given set of points. Moreover, on integer grid point sets or random point sets our algorithm achieves a low constant \($\beta$\). Besides these results for the Euclidean model, we discuss a generalization of our algorithm to instances with arbitrary, even non-metric, edge lengths. Moreover, in contrast to these algorithmic results, we show that no such positive results are possible when focusing on either optimal networks, i.e., \($(\beta,1)$\)-networks, or perfectly stable networks, i.e., \($(1,\gamma)$\)-networks, as in both cases NP-hard problems arise, there exist instances with very unstable optimal networks, and there are instances for perfectly stable networks with high total cost. Along the way, we significantly improve several results from Bilò et al. and we asymptotically resolve their conjecture about the Price of Anarchy by providing a tight bound.
@inproceedings{friedemann2021efficiency, abstract = {Network Design problems typically ask for a minimum cost sub-network from a given host network. This classical point-of-view assumes a central authority enforcing the optimum solution. But how should networks be designed to cope with selfish agents that own parts of the network? In this setting, minimum cost networks may be very unstable in that agents will deviate from a proposed solution if this decreases their individual cost. Hence, designed networks should be both efficient in terms of total cost and stable in terms of the agents' willingness to accept the network. We study this novel type of Network Design problem by investigating the creation of $(\beta,\gamma)$-networks, that are in $\beta$-approximate Nash equilibrium and have a total cost of at most $\gamma$ times the optimal cost, for the recently proposed Euclidean Generalized Network Creation Game by Bilò et al.SPAA2019. There, $n$ agents corresponding to points in Euclidean space create costly edges among themselves to optimize their centrality in the created network. Our main result is a simple $\mathcal{O}(n^2)$-time algorithm that computes a $(\beta,\beta)$-network with low $\beta$ for any given set of points. Moreover, on integer grid point sets or random point sets our algorithm achieves a low constant $\beta$. Besides these results for the Euclidean model, we discuss a generalization of our algorithm to instances with arbitrary, even non-metric, edge lengths. Moreover, in contrast to these algorithmic results, we show that no such positive results are possible when focusing on either optimal networks, i.e., $(\beta,1)$-networks, or perfectly stable networks, i.e., $(1,\gamma)$-networks, as in both cases NP-hard problems arise, there exist instances with very unstable optimal networks, and there are instances for perfectly stable networks with high total cost. Along the way, we significantly improve several results from Bilò et al. and we asymptotically resolve their conjecture about the Price of Anarchy by providing a tight bound.}, author = {Friedemann, Wilhelm and Friedrich, Tobias and Gawendowicz, Hans and Lenzner, Pascal and Melnichenko, Anna and Peters, Jannik and Stephan, Daniel and Vaichenker, Michael}, booktitle = {Symposium on Parallelism in Algorithms and Architectures (SPAA)}, keywords = {sys:relevantfor:ae annamelnichenko hansgawendowicz pascallenzner spaa tobiasfriedrich year2021}, pages = {232–242}, publisher = {ASM}, title = {Efficiency and Stability in Euclidean Network Design}, year = 2021 }

2020 [ nach oben ]

Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes; Melnichenko, Anna Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programmingTheoretical Computer Science 2020: 96–113
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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.
@article{ktzing2020destructiveness, abstract = {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.}, author = {Kötzing, Timo and Lagodzinski, J. A. Gregor and Lengler, Johannes and Melnichenko, Anna}, journal = {Theoretical Computer Science}, keywords = {annamelnichenko gregorlagodzinski johanneslengler tcs timokoetzing year2020}, pages = {96–113}, title = {Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming}, volume = 816, year = 2020 }

Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna; Molitor, Louise Fair Tree Connection Games with Topology-Dependent Edge CostFoundations of Software Technology and Theoretical Computer Science (FSTTCS) 2020: 15:1–15:15
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
How do rational agents self-organize when trying to connect to a common target? We study this question with a simple tree formation game which is related to the well-known fair single-source connection game by Anshelevich et al.(FOCS'04) and selfish spanning tree games by Gourvès and Monnot (WINE'08). In our game agents correspond to nodes in a network that activate a single outgoing edge to connect to the common target node (possibly via other nodes). Agents pay for their path to the common target, and edge costs are shared fairly among all agents using an edge. The main novelty of our model is dynamic edge costs that depend on the in-degree of the respective endpoint. This reflects that connecting to popular nodes that have increased internal coordination costs is more expensive since they can charge higher prices for their routing service. In contrast to related models, we show that equilibria are not guaranteed to exist, but we prove the existence for infinitely many numbers of agents. Moreover, we analyze the structure of equilibrium trees and employ these insights to prove a constant upper bound on the Price of Anarchy as well as non-trivial lower bounds on both the Price of Anarchy and the Price of Stability. We also show that in comparison with the social optimum tree the overall cost of an equilibrium tree is more fairly shared among the agents. Thus, we prove that self-organization of rational agents yields on average only slightly higher cost per agent compared to the centralized optimum, and at the same time, it induces a more fair cost distribution. Moreover, equilibrium trees achieve a beneficial trade-off between a low height and low maximum degree, and hence these trees might be of independent interest from a combinatorics point-of-view. We conclude with a discussion of promising extensions of our model.
@inproceedings{bilo2020connection, abstract = {How do rational agents self-organize when trying to connect to a common target? We study this question with a simple tree formation game which is related to the well-known fair single-source connection game by Anshelevich et al.(FOCS'04) and selfish spanning tree games by Gourvès and Monnot (WINE'08). In our game agents correspond to nodes in a network that activate a single outgoing edge to connect to the common target node (possibly via other nodes). Agents pay for their path to the common target, and edge costs are shared fairly among all agents using an edge. The main novelty of our model is dynamic edge costs that depend on the in-degree of the respective endpoint. This reflects that connecting to popular nodes that have increased internal coordination costs is more expensive since they can charge higher prices for their routing service. In contrast to related models, we show that equilibria are not guaranteed to exist, but we prove the existence for infinitely many numbers of agents. Moreover, we analyze the structure of equilibrium trees and employ these insights to prove a constant upper bound on the Price of Anarchy as well as non-trivial lower bounds on both the Price of Anarchy and the Price of Stability. We also show that in comparison with the social optimum tree the overall cost of an equilibrium tree is more fairly shared among the agents. Thus, we prove that self-organization of rational agents yields on average only slightly higher cost per agent compared to the centralized optimum, and at the same time, it induces a more fair cost distribution. Moreover, equilibrium trees achieve a beneficial trade-off between a low height and low maximum degree, and hence these trees might be of independent interest from a combinatorics point-of-view. We conclude with a discussion of promising extensions of our model.}, author = {Bilò, Davide and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna and Molitor, Louise}, booktitle = {Foundations of Software Technology and Theoretical Computer Science (FSTTCS)}, keywords = {annamelnichenko fsttcs louisemolitor pascallenzner tobiasfriedrich year2020}, pages = {15:1–15:15}, publisher = {Schloss Dagstuhl–Leibniz-Zentrum f{ü}r Informatik}, title = {Fair Tree Connection Games with Topology-Dependent Edge Cost}, volume = 182, year = 2020 }

Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna Flow-Based Network Creation GamesInternational Joint Conference on Artificial Intelligence (IJCAI) 2020: 139–145
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Network Creation Games (NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selfishly decide with whom to connect to optimize some objective function. Past research intensively analyzed models where the agents strive for a central position in the network. This models agents optimizing the network for low-latency applications like VoIP. However, with today's abundance of streaming services it is important to ensure that the created network can satisfy the increased bandwidth demand. To the best of our knowledge, this natural problem of the decentralized strategic creation of networks with sufficient bandwidth has not yet been studied. We introduce Flow-Based NCGs where the selfish agents focus on bandwidth instead of latency. In essence, budget-constrained agents create network links to maximize their minimum or average network flow value to all other network nodes. Equivalently, this can also be understood as agents who create links to increase their connectivity and thus also the robustness of the network. For this novel type of NCG we prove that pure Nash equilibria exist, we give a simple algorithm for computing optimal networks, we show that the Price of Stability is~1 and we prove an (almost) tight bound of 2 on the Price of Anarchy. Last but not least, we show that our models do not admit a potential function.
@inproceedings{echzell2020flowbased, abstract = {Network Creation Games (NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selfishly decide with whom to connect to optimize some objective function. Past research intensively analyzed models where the agents strive for a central position in the network. This models agents optimizing the network for low-latency applications like VoIP. However, with today's abundance of streaming services it is important to ensure that the created network can satisfy the increased bandwidth demand. To the best of our knowledge, this natural problem of the decentralized strategic creation of networks with sufficient bandwidth has not yet been studied. We introduce Flow-Based NCGs where the selfish agents focus on bandwidth instead of latency. In essence, budget-constrained agents create network links to maximize their minimum or average network flow value to all other network nodes. Equivalently, this can also be understood as agents who create links to increase their connectivity and thus also the robustness of the network. For this novel type of NCG we prove that pure Nash equilibria exist, we give a simple algorithm for computing optimal networks, we show that the Price of Stability is 1 and we prove an (almost) tight bound of 2 on the Price of Anarchy. Last but not least, we show that our models do not admit a potential function.}, author = {Echzell, Hagen and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, editor = {Bessiere, Christian}, keywords = {annamelnichenko hagenechzell ijcai pascallenzner tobiasfriedrich year2020}, pages = {139-145}, publisher = {ijcai.org}, title = {Flow-Based Network Creation Games}, year = 2020 }

2019 [ nach oben ]

Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna Geometric Network Creation GamesSymposium on Parallelism in Algorithms and Architectures (SPAA) 2019: 323–332
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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.
@inproceedings{bil2019geometric, abstract = {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.}, author = {Bilò, Davide and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {Symposium on Parallelism in Algorithms and Architectures (SPAA)}, keywords = {annamelnichenko davidebilo pascallenzner spaa tobiasfriedrich year2019}, pages = {323-332}, title = {Geometric Network Creation Games}, year = 2019 }

2018 [ nach oben ]

Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes; Melnichenko, Anna Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic ProgrammingParallel Problem Solving From Nature (PPSN) 2018: 42–54
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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 ConcatenationCrossover GP. For this purpose three variants of the well-studied 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.
@inproceedings{kotzing2018destructiveness, abstract = {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 ConcatenationCrossover GP. For this purpose three variants of the well-studied 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.}, author = {Kötzing, Timo and Lagodzinski, J. A. Gregor and Lengler, Johannes and Melnichenko, Anna}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {annamelnichenko gregorlagodzinski johanneslengler ppsn timokoetzing year2018}, pages = {42-54}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming}, volume = 11102, year = 2018 }

2017 [ nach oben ]

Friedrich, Tobias; Kötzing, Timo; Melnichenko, Anna Analyzing Search Heuristics with Differential EquationsGenetic and Evolutionary Computation Conference (GECCO) 2017: 313–314
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Drift Theory is currently the most common technique for the analysis of randomized search heuristics because of its broad applicability and the resulting tight first hitting time bounds. The biggest problem when applying a drift theorem is to find a suitable potential function which maps a complex space into a single number, capturing the essence of the state of the search in just one value. We discuss another method for the analysis of randomized search heuristics based on the Theory of Differential Equations. This method considers the deterministic counterpart of the randomized process by replacing probabilistic outcomes by their expectation, and then bounding the error with good probability. We illustrate this by analyzing an Ant Colony Optimization algorithm (ACO) for the Minimum Spanning Tree problem (MST).
@inproceedings{friedrich2017analyzing, abstract = {Drift Theory is currently the most common technique for the analysis of randomized search heuristics because of its broad applicability and the resulting tight first hitting time bounds. The biggest problem when applying a drift theorem is to find a suitable potential function which maps a complex space into a single number, capturing the essence of the state of the search in just one value. We discuss another method for the analysis of randomized search heuristics based on the Theory of Differential Equations. This method considers the deterministic counterpart of the randomized process by replacing probabilistic outcomes by their expectation, and then bounding the error with good probability. We illustrate this by analyzing an Ant Colony Optimization algorithm (ACO) for the Minimum Spanning Tree problem (MST).}, author = {Friedrich, Tobias and Kötzing, Timo and Melnichenko, Anna}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {annamelnichenko gecco timokoetzing tobiasfriedrich year2017}, pages = {313-314}, title = {Analyzing Search Heuristics with Differential Equations}, year = 2017 }

Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Molitor, Louise Selfish Network Creation with Non-Uniform Edge CostSymposium on Algorithmic Game Theory (SAGT) 2017: 160–172
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC’03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games. We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has con- stant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.
@inproceedings{chauhan2017selfish, abstract = {Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC’03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games. We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has con- stant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.}, author = {Chauhan, Ankit and Lenzner, Pascal and Melnichenko, Anna and Molitor, Louise}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, keywords = {ankitchauhan annamelnichenko louisemolitor pascallenzner sagt year2017}, pages = {160-172}, title = {Selfish Network Creation with Non-Uniform Edge Cost}, year = 2017 }

2016 [ nach oben ]

Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Münn, Martin On Selfish Creation of Robust NetworksSymposium on Algorithmic Game Theory (SAGT) 2016: 141–152
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Robustness is one of the key properties of nowadays networks. However, robustness cannot be simply enforced by design or regulation since many important networks, most prominently the Internet, are not created and controlled by a central authority. Instead, Internet-like networks emerge from strategic decisions of many selfish agents. Interestingly, although lacking a coordinating authority, such naturally grown networks are surprisingly robust while at the same time having desirable properties like a small diameter. To investigate this phenomenon we present the first simple model for selfish network creation which explicitly incorporates agents striving for a central position in the network while at the same time protecting themselves against random edge-failure. We show that networks in our model are diverse and we prove the versatility of our model by adapting various properties and techniques from the non-robust versions which we then use for establishing bounds on the Price of Anarchy. Moreover, we analyze the computational hardness of finding best possible strategies and investigate the game dynamics of our model.
@inproceedings{Chauhan2016, abstract = {Robustness is one of the key properties of nowadays networks. However, robustness cannot be simply enforced by design or regulation since many important networks, most prominently the Internet, are not created and controlled by a central authority. Instead, Internet-like networks emerge from strategic decisions of many selfish agents. Interestingly, although lacking a coordinating authority, such naturally grown networks are surprisingly robust while at the same time having desirable properties like a small diameter. To investigate this phenomenon we present the first simple model for selfish network creation which explicitly incorporates agents striving for a central position in the network while at the same time protecting themselves against random edge-failure. We show that networks in our model are diverse and we prove the versatility of our model by adapting various properties and techniques from the non-robust versions which we then use for establishing bounds on the Price of Anarchy. Moreover, we analyze the computational hardness of finding best possible strategies and investigate the game dynamics of our model.}, address = {Berlin, Heidelberg}, author = {Chauhan, Ankit and Lenzner, Pascal and Melnichenko, Anna and Münn, Martin}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, editor = {Gairing, Martin and Savani, Rahul}, keywords = {ankitchauhan annamelnichenko pascallenzner sagt year2016}, pages = {141-152}, publisher = {Springer Berlin Heidelberg}, title = {On Selfish Creation of Robust Networks}, year = 2016 }