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.
A part of our work focuses on tree networks. Such topologies are common outcomes of NCGs if edges are expensive, which led the authors of @cite_3 to conjecture that all (non-transient) stable networks of NCGs are trees if @math is greater than some constant. The conjecture was later disproved by @cite_4 but it was shown to be true for high edge-cost. In particular, the authors of @cite_2 proved that all stable networks are trees if @math in the version or if @math in the version. Experimental evidence suggests that this transition to tree networks already happens at much lower edge-cost and it is an interesting open problem to improve on these bounds.
@cite_4 @cite_3 @cite_2
2032349632 2594715668
We study a network creation game recently proposed by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game, each player (vertex) can create links (edges) to other players at a cost of α per edge. The goal of every player is to minimize the sum consisting of (a) the cost of the links he has created and (b) the sum of the distances to all other players. conjectured that there exists a constant A such that, for any α > A, all non-transient Nash equilibria graphs are trees. They showed that if a Nash equilibrium is a tree, the price of anarchy is constant. In this paper we disprove the tree conjecture. More precisely, we show that for any positive integer n 0 , there exists a graph built by n ≥ n 0 players which contains cycles and forms a non-transient Nash equilibrium, for any α with 1 < α ≤ √n 2. Our construction makes use of some interesting results on finite affine planes. On the other hand we show that, for α ≥ 12n[log n], every Nash equilibrium forms a tree.Without relying on the tree conjecture, proved an upper bound on the price of anarchy of O(√α), where α ∈ [2, n2]. We improve this bound. Specifically, we derive a constant upper bound for α ∈ O(√n) and for α ≥ 12n[log n]. For the intermediate values we derive an improved bound of O(1 + (min α2 n, n2 α )1 3).Additionally, we develop characterizations of Nash equilibria and extend our results to a weighted network creation game as well as to scenarios with cost sharing. We study the price of anarchy and the structure of equilibria in network creation games. A network creation game (first defined and studied by [4]) is played by n players 1, 2, . . . , n , each identified with a vertex of a graph (network), where the strategy of player i, i = 1, . . . , n, is to build some edges adjacent to i. The cost of building an edge is α > 0, a fixed parameter of the game. The goal of every player is to minimize its creation cost plus its usage cost. The creation cost of player i is α times the number of built edges. In the SumGame (the original variant of [4]) the usage cost of player i is the sum of distances from i to every node of the resulting graph. In the MaxGame (variant defined and studied by [3]) the usage cost is the eccentricity of i in the resulting graph of the game. In this paper we improve previously known bounds on the price of anarchy of the game (of both variants) for various ranges of α, and give new insights into the structure of equilibria for various values of α. The two main results of the paper show that for α > 273 · n all equilibria in SumGame are trees and thus the price of anarchy is constant, and that for α > 129 all equilibria in MaxGame are trees and the price of anarchy is constant. For SumGame this (almost) answers one of the basic open problems in the field – is price of anarchy of the network creation game constant for all values of α? – in an affirmative way, up to a tiny range of α.