Network creation games: structure vs anarchy

Abstract

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.

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