[en] 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^(1-6)) = 1/(log(n)), and for a > 4n-13. 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(1+E) 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 <n/C with C>4 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 <n/C with C>4 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.

[es] En un intento para entender como redes de naturaleza similar a las del Internet y las redes sociales se comportan, al largo de la historia se han propuesto y estudiado modelos que tratan de capturar los aspectos y las propiedades más esenciales. Los juegos de formación de redes son una clase de juegos estratégicos muy estudiados en la teoría de juegos algorítmica que modelizan estas redes como el resultado de la interacción descentralizada de los agentes que la integran. En estos juegos los distintos jugadores modelizan agentes egoístas que compran enlaces hacia los otros jugadores intentando minimizar una función individual. Este coste se modeliza como una función que se descompone en el coste de creación (coste relativo a la compra de los enlaces del mismo jugador) y, en segundo lugar, el coste de utilización (mesura de la cualidad de conexión a la red resultante). Debido al comportamiento egoísta de los agentes, las situaciones estables que se consiguen, los llamados equilibrios de Nash, no coinciden necesariamente con las configuraciones óptimas des del punto de vista social que se podrían establecer si existiera una entidad centralizadora que tomara una decisión por todos los jugadores. Justamente, el precio de la anarquía es la medida que cuantifica la diferencia que hay entre los equilibrios de Nash más costosos versus el óptimo des del punto de vista social. En esta tesis, estudiaremos estos dos conceptos claves, el precio de la anarquía y los equilibrios de Nash en escenarios y situaciones diferentes, con la intención de entender mejor como el comportamiento egoísta de los agentes de estas redes afecta su cualidad. Proponemos dos perspectivas distintas para este estudio. En primer lugar, estudiamos uno de los modelos más emblemáticos de los juegos de formación de redes que llamamos sum classical network creation game. Este es un modelo de redes que se basa en dos parámetros distintos: n, el número de nodos de la red, y _, una función de n que modeliza el precio por enlace. Al largo del tiempo se ha demostrado que el precio de la anarquía es constante para α= O (n1-δ ) y δ ≥1 log/n, como para α > 4n-13. Además se ha conjeturado que el precio de la anarquía es constante independientemente del parámetro α. Respecto al rango α< n=C con C > 4 constante, sabemos que los equilibrios inducen una clase de grafos que se llama distancia-uniforme. En esta primera parte se demuestra, primero, que el precio de la anarquía es constante incluso cuando α> n(1 + ε) con ε > 0 con ε > 0 cualquier constante positiva engrandeciendo, pues, el rango de valores del parámetro _ por los cuales el precio de la anarquía es constante. En segundo lugar, se estudia el diámetro de los grafos distancia-uniforme en un intento de obtener información sobre la topología de los equilibrios para el rango α < n=C con C > 4 constante. El segundo punto de vista que consideremos consiste en proponer y estudiar dos modelos de creación de redes nuevos que llamamos los celebrity games. Estos dos modelos parten del análisis de las redes descentralizadas con agentes heterogéneos, como puede ser el caso de agentes que tienen distintos grados de relevancia dentro de la red correspondiente, una característica hasta ahora poco estudiada en los modelos de la literatura. Para capturar esta característica natural se introducen pesos para cada agente de la red. Por otro lado, otra característica que se considera en la propuesta de estos dos modelos nuevos es el concepto de distancia crítica que captura el nivel _ a partir del cual, nodos que estén más lejanos que el valor _ del jugador en consideración penalizan a tal jugador. Así, lo que se persigue en estos dos nuevos modelos es tener el mínimo número de enlaces posibles y al mismo tiempo minimizar la máxima de las penalizaciones de los jugadores más lejanos de Β de acuerdo con sus pesos. Los dos modelos que estudiamos se diferencian en cómo se calcula la afectación o penalización de los jugadores más lejanos de Β. Para los dos modelos obtenemos cotas superiores e inferiores del precio de la anarquía, así como las propiedades y características topológicas principales de los equilibrios.