Resumen de Network creation games: structure vs anarchy
Arnau Messegué Buisan
In an attempt to understand how Internet-like network and social networks behave, different models have been proposed and studied throughout history to capture their most essential aspects and properties. Network Creation Games are a class of strategic games widely studied in Algorithmic Game Theory that model these networks as the outcome of decentralised and uncoordinated interactions. In these games the different players model selfish agents that buy links towards the other agents trying to minimise an individual function. This cost is modelled as a function that usually decomposes into the creation cost (cost of buying links) and the usage cost (measuring the quality of the connection to the network). Due to the agents' selfish behaviour, stable configurations in which all players are happy with the current situation, the so-called Nash equilibria, do not have to coincide with any socially optimal configuration that could be established if a centralised authority could decide by all players. In this way, the price of anarchy is the measure that quantifies precisely the ratio between the most costly Nash equilibrium versus any optimal network from a social point of view.
In this work, we study the price of anarchy and Nash equilibria in different scenarios and situations, in order to better understand how the selfish behaviour of agents in these networks affects their quality of the resulting networks. We propose this study from two different perspectives.
In the first one, we study one of the most emblematic models of Network Creation Games called sum classical network creation game. This is a model that is based on two different parameters: n, the number of nodes, and a, a function of n that models the price per link. Throughout history it has been shown that the price of anarchy is constant for a =O(n(16)) = 1/(log(n)), and for a >4n13. It has been conjectured that the price of anarchy is constant regardless of the parameter a. In this first part we show, first of all, that the price of anarchy is constant even when a n(1E) with =0 any positive constant, thus enlarging the range of values a for which the price of anarchy is constant. Secondly, regarding the range a nC with C4 any positive constant, we know that equilibria induce a class of graphs called distance-uniform. Then, we study the diameter of the distance-uniform graphs in an attempt to obtain information about the topology of equilibria for the range a< n/C with C>4 any positive constant. Secondly, we study the diameter of the distance-uniform graphs in an attempt to obtain information about the topology of the equilibria for the range a nC with C4 any positive constant.
In the second perspective we propose and study two new models that we call celebrity games. These two models are based on the analysis of decentralized networks with heterogeneous players, that is, players with different degrees of relevance within the corresponding network, a feature that has not been studied in much detail in the literature. To capture this natural property, we introduce a weight for each player in the network. Furthermore, these models take into account a critical distance B, a threshold value. Each player aim to be not farther than ß from the other players and decides whether to buy links to other players depending on the price per link and their corresponding weights. Moreover, the larger is the weight of a player farther than B, larger is the corresponding penalty. Thus, in these new models players strive to have the minimum possible number of links and at the same time they want to minimise as much as possible the penalty for having players farther from B. They differ in how the penalty corresponding to the players further than ß is computed. For both models we obtain upper and lower bounds of the price of anarchy as well as the main topological properties and characteristics of their equilibria.
