We introduce and analyze greedy equilibria (GE) for the well-known model of selfish network creation by [PODC'03]. GE are interesting for two reasons: (1) they model outcomes found by agents which prefer smooth adaptations over radical strategy-changes, (2) GE are outcomes found by agents which do not have enough computational resources to play optimally. In the model of agents correspond to Internet Service Providers which buy network links to improve their quality of network usage. It is known that computing a best response in this model is NP-hard. Hence, poly-time agents are likely not to play optimally. But how good are networks created by such agents? We answer this question for very simple agents. Quite surprisingly, naive greedy play suffices to create remarkably stable networks. Specifically, we show that in the SUM version, where agents attempt to minimize their average distance to all other agents, GE capture Nash equilibria (NE) on trees and that any GE is in 3-approximate NE on general networks. For the latter we also provide a lower bound of 3 2 on the approximation ratio. For the MAX version, where agents attempt to minimize their maximum distance, we show that any GE-star is in 2-approximate NE and any GE-tree having larger diameter is in 6 5-approximate NE. Both bounds are tight. We contrast these positive results by providing a linear lower bound on the approximation ratio for the MAX version on general networks in GE. This result implies a locality gap of @math for the metric min-max facility location problem, where n is the number of clients.
@cite_13 investigated NCGs, where agents cannot buy every possible edge. Furthermore, @cite_17 recently analyzed a bounded-budget version. Both versions seem realistic, but in the following we do not restrict the set of edges which can be bought or the budget of an agent. Clearly, such restrictions reduce the qualitative gap between simple and arbitrary strategy-changes and would lead to weaker results for our analysis. Note, that this indicates that outcomes found by simple agents in the edge or budget-restricted version may be even more stable than we show in the following sections.
@cite_13 @cite_17
2117907411 2132936659
A fundamental family of problems at the intersection between computer science and operations research is network design. This area of research has become increasingly important given the continued growth of computer networks such as the Internet. Traditionally, we want to find a minimum-cost (sub)network that satisfies some specified property such as k-connectivity or connectivity on terminals (as in the classic Steiner tree problem). This goal captures the (possibly incremental) creation cost of the network, but does not incorporate the cost of actually using the network. In contrast, network routing has the goal of optimizing the usage cost of the network, but assumes that the network has already been created. We consider a network creation game in which, each player (vertex) has a limited budget to establish links to other players. In our model, each link has a unit cost and each agent tries to minimize its cost which is its local diameter or its total distance to other players in the (undirected) underlying graph of the created network. Two variants of the game are studied: in the MAX version, the cost incurred to a vertex is the maximum distance between that vertex and other vertices, and in the SUM version, the cost incurred to a vertex is the sum of distances between that vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard. Next, we study the maximum possible diameter of an equilibrium graph with n vertices in various cases. For infinite numbers of n, we construct an equilibrium tree with diameter Θ(n) in the MAX version. Also, we prove that the diameter of any equilibrium tree is O(log n) in the SUM version and this bound is tight. When all vertices have unit budgets (i.e. can establish link to just one vertex), the diameter in both versions is O(1). We give an example of equilibrium graph in MAX version, such that all vertices have positive budgets and yet the diameter is as large as Ω(√log n). This interesting result shows that the diameter does not decrease necessarily and may increase as the budgets are increased. For the SUM version, we prove that every equilibrium graph has diameter 2O(√log n) when all vertices have positive budgets. Moreover, if the budget of every players is at least k, then every equilibrium graph with diameter more than 3 is k-connected.