Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by [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 constant 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.
Several versions for augmenting the NCG with locality have been proposed and analyzed recently. It was shown that the PoA may deteriorate heavily if agents only know their local neighborhood or only a shortest path tree of the network @cite_8 @cite_24 . In contrast, a global view with a restriction to only local edge-purchases yields only a moderate increase of the PoA @cite_12 .
@cite_24 @cite_12 @cite_8
79855918 2949981324
Network creation games model the autonomous formation of an interconnected system of selfish users. In particular, when the network will serve as a digital communication infrastructure, each user is identified by a node of the network, and contributes to the build-up process by strategically balancing between her building cost (i.e., the number of links she personally activates in the network) and her usage cost (i.e., some function of the distance in the sought network to the other players). When the corresponding game is analyzed, the generally adopted assumption is that players have a common and complete information about the evolving network topology, which is quite unrealistic though, due to the massive size this may have in practice. In this paper, we thus relax this assumption, by instead letting the players have only a partial knowledge of the network. To this respect, we make use of three popular traceroute-based knowledge models used in network discovering (i.e., the activity of reconstructing the topology of an unknown network through queries at its nodes), namely: (i) distance vector, (ii) shortest-path tree view, and (iii) layered view. For all these models, we provide exhaustive answers to the canonical algorithmic game theoretic questions: convergence, computational complexity for a player of selecting a best response, and tight bounds to the price of anarchy, all of them computed w.r.t. a suitable (and unifying) equilibrium concept. We investigate a non-cooperative game-theoretic model for the formation of communication networks by selfish agents. Each agent aims for a central position at minimum cost for creating edges. In particular, the general model (, PODC'03) became popular for studying the structure of the Internet or social networks. Despite its significance, locality in this game was first studied only recently (Bil , SPAA'14), where a worst case locality model was presented, which came with a high efficiency loss in terms of quality of equilibria. Our main contribution is a new and more optimistic view on locality: agents are limited in their knowledge and actions to their local view ranges, but can probe different strategies and finally choose the best. We study the influence of our locality notion on the hardness of computing best responses, convergence to equilibria, and quality of equilibria. Moreover, we compare the strength of local versus non-local strategy-changes. Our results address the gap between the original model and the worst case locality variant. On the bright side, our efficiency results are in line with observations from the original model, yet we have a non-constant lower bound on the price of anarchy.