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 [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.
There are many classical optimization problems related to network design, e.g. see the survey by Magnanti & Wong @cite_1 . Many of them are NP-complete, e.g. all the problems labeled ND'' in @cite_39 . Our model is closely related to the Network Design Problem @cite_21 and the Optimum Communication Spanning Tree Problem (ND7 in @cite_39 ). In particular, finding the social optimum network corresponds to a variant of the Network Design Problem, where, instead of having separate budgets for buying edges and for the routing cost, the sum of edge costs and routing costs, i.e., the total distance between all pairs of nodes, is to be minimized. Hence we strongly suspect that computing the social optimum in all versions of our model, with the and the as exceptions, is NP-hard.
@cite_21 @cite_1 @cite_39
2016218947 2171985270
We consider the problem of reducing the edge lengths of a given network so that the modified network has a spanning tree of small total length. It is assumed that each edge e of the given network has an associated function C sub e that specifies the cost of shortening the edge by a given amount and that there is a budget B on the total reduction cost. The goal is to develop a reduction strategy satisfying the budget constraint so that the total length of a minimum spanning tree in the modified network is the smallest possible over all reduction strategies that obey the budget constraint. We show that in general the problem of computing optimal reduction strategy for modifying the network as above in NP-hard and present the first polynomial time approximation algorithms for the problem, where the cost functions C sub e are allowed to be taken from a broad class of functions. We also present improved approximation algorithms for the class of treewidth-bounded graphs when the cost functions are linear. Our results can be extended to obtain approximation algorithms for more general network design problems such as those considered in [GW, GG+94]. In the network design problem we are given a weighted undirected graph. We wish to find a subgraph which connects all the original vertices and minimizes the sum of the shortest path weights between all vertex pairs, subject to a budget constraint on the sum of its edge weights. In this note we establish NP-completeness for the network design problem, even for the simple case where all edge weights are equal and the budget restricts the choice to spanning trees. This result justifies the development of enumerative optimization methods and of approximation algorithms, such as those described in a recent paper by R. Dionne and M. Florian. We study network-design problems with multiple design objectives. In particular, we look at two cost measures to be minimized simultaneously: the total cost of the network and the maximum degree of any node in the network. Our main result can be roughly stated as follows: given an integer @math , we present approximation algorithms for a variety of network-design problems on an @math -node graph in which the degree of the output network is @math and the cost of this network is @math times that of the minimum-cost degree- @math -bounded network. These algorithms can handle costs on nodes as well as edges. Moreover, we can construct such networks so as to satisfy a variety of connectivity specifications including spanning trees, Steiner trees and generalized Steiner forests. The performance guarantee on the cost of the output network is nearly best-possible unless @math . We also address the special case in which the costs obey the triangle inequality. In this case, we obtain a polynomial-time approximation algorithm with a stronger performance guarantee. Given a bound @math on the degree, the algorithm finds a degree- @math -bounded network of cost at most a constant time optimum. There is no algorithm that does as well in the absence of triangle inequality unless @math . We also show that in the case of spanning networks, we can simultaneously approximate within a constant factor yet another objective: the maximum cost of any edge in the network, also called the bottleneck cost of the network. We extend our algorithms to find TSP tours and @math -connected spanning networks for any fixed @math that simultaneously approximate all these three cost measures.