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

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