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.
To the best of our knowledge, approximate Nash equilibria have not been studied before in the context of selfish network creation. Closest to our approach here may be the work of @cite_14 , which analyzes for a related game how tolerant the agents have to be in order to accept a centrally designed solution. We adopt a similar point of view by asking how tolerant agents have to be to accept a solution found by greedy play.
@cite_14
1974040162
In this paper, we study a basic network design game in which n self-interested agents, each having individual connectivity requirements, wish to build a network by purchasing links from a given set of edges. A fundamental cost-sharing mechanism is Shapley cost-sharing, which splits the cost of an edge in a fair manner among the agents using the edge. It is well known that in such games, the price of anarchy is n, while the price of stability is H(n), where H(n) denotes the nth harmonic number. We investigate whether an optimal minimum-cost network represents an attractive, relatively stable state that agents might want to purchase: what extra cost does an agent incur compared to a possible strategy deviation? We employ the concept of α-approximate Nash equilibria, in which no agent can reduce its cost by a factor of more than α. We prove that for single-source games in undirected graphs, every optimal network represents an H(n)-approximate Nash equilibrium. We show that this bound is tight by presenting a...