[ca] En un intent per entendre com xarxes de naturalesa similar a les de l'Internet i les xarxes socials es comporten, al llarg de la història s'han proposat i estudiat diferents models que tracten de capturar-ne els aspectes i les propietats més essencials. Els jocs de formació de xarxes són una classe de jocs estratègics molt estudiats en teoria de jocs algorísmica que modelitzen aquestes xarxes com el resultat de la interacció descentralitzada dels agents que la integren. En aquests jocs els diferents jugadors modelitzen agents egoistes que compren enllaços cap als altres jugadors intentant minimitzar una funció individual. Aquest cost es modela com una funció que es descomposa en dues components: el cost de creació (cost relatiu a la compra dels enllaços del mateix jugador) i, en segon lloc, el cost d'utilització (mesura de la qualitat de connexió a la xarxa resultant). Degut al comportament egoista dels agents, les situacions estables que s'assoleixen, els anomenats equilibris de Nash, no tenen per què coincidir amb les configuracions òptimes des del punt de vista social que es podrien establir si existeix una entitat centralitzadora que decideix per tots els jugadors. Justament, el preu de l'anarquia és la mesura que quantifica la diferència que hi ha entre l'equilibri de Nash més costós versus l'òptim des del punt de vista social. En aquesta tesis, estudiarem aquests dos conceptes claus, el preu de l'anarquia i els equilibris de Nash, en escenaris i situacions diferents, per tal d'entendre millor com el comportament egoista dels agents d'aquestes xarxes n'afecta la seva qualitat. Proposem dues perspectives diferents a aquest estudi. En primer lloc, estudiem un dels models més emblemàtics dels jocs de formació de xarxes que anomenem sum classical network creation game. Aquest és un model de xarxes que es basa en dos paràmetres diferents: n, nombre de nodes, i α, una funció de n que modelitza el preu per enllaç. Al llarg de la història s'ha demostrat que el preu de l'anarquia és constant per a α= O (n1-δ ) i δ ≥1 log/n, així com per a α > 4n-13. A més s'ha conjecturat que el preu de l'anarquia és constant independentment del paràmetre α . Pel que fa al rang α< n=C amb C > 4 constant, sabem que els equilibris indueixen una classe de grafs que s'anomenen distance-uniform. En aquesta primera part es demostra, en primer lloc, que el preu de l'anarquia és constant inclús quan α> n(1 + ε) amb ε > 0 qualsevol constant positiva allargant, doncs, el rang de valors del paràmetre α pels quals el preu d'anarquia és constant. En segon lloc, s'estudia el diàmetre dels grafs distance-uniform en un intent d'obtenir informació sobre la topologia dels equilibris per al rang α < n=C amb C > 4 constant. El segon punt de vista que considerem consisteix en proposar i estudiar dos nous models de creació de xarxes que anomenem els celebrity games. Aquests dos models parteixen de l'anàlisi de les xarxes decentralitzades amb agents heterogenis, com és el cas d'agents que tenen diferents graus de rellevància dins de la xarxa corresponent, un tret fins ara poc estudiat en els models de la literatura. Per capturar aquesta característica natural s'introdueixen pesos, un per a cada agent de la xarxa. D'altra banda, una altra característica que es considera en la proposta d'aquests dos models nous és el concepte de distància critica que captura el llindar Β a partir del qual, nodes que estiguin més llunyans que el valor B del jugador en consideració penalitzen a tal jugador. Així, el que es persegueix en aquests dos nous models és tenir el mínim nombre d'enllaços possibles i al mateix temps, minimitzar el màxim possible la penalització dels jugadors més llunyans de Β d'acord amb els seus pesos. Els dos models que estudiem es diferencien en com es calcula l'afectació o penalització dels jugadors més llunyans de Β. Pels dos models obtenim fites superiors i inferiors del preu de l'anarquia així com les propietats i característiques topològiques principals dels equilibris.

[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.