Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/83229

Stars and celebrities: A network creation game
Álvarez Faura, M. del Carme; Blesa Aguilera, Maria Josep; Duch Brown, Amalia; Messegué Buisan, Arnau; Serna Iglesias, María José
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
CoRR
Celebrity games, a new model of network creation games is introduced. The specific features of this model are that players have different celebrity weights and that a critical distance is taken into consideration. The aim of any player is to be close (at distance less than critical) to the others, mainly to those with high celebrity weights. The cost of each player depends on the cost of establishing direct links to other players and on the sum of the weights of those players at a distance greater than the critical distance. We show that celebrity games always have pure Nash equilibria and we characterize the family of subgames having connected Nash equilibria, the so called star celebrity games. Exact bounds for the PoA of non star celebrity games and a bound of O(n/ß+ß) for star celebrity games are provided. The upper bound on the PoA can be tightened when restricted to particular classes of Nash equilibria graphs. We show that the upper bound is O(n/ß) in the case of 2-edge-connected graphs and 2 in the case of trees.
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
Graph theory
Social networks
Network Creation Games
Grafs, Teoria de
Xarxes socials
Artículo - Borrador
Informe
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Álvarez Faura, M. del Carme; Duch Brown, Amalia; Gabarró Vallès, Joaquim; Serna Iglesias, María José
Álvarez Faura, M. del Carme; Duch Brown, Amalia; Serna Iglesias, María José; Thilikos Touloupas, Dimitrios
Álvarez Faura, M. del Carme; Duch Brown, Amalia; Gabarró Vallès, Joaquim; Serna Iglesias, María José
Álvarez Faura, M. del Carme; Duch Brown, Amalia; Gabarró Vallès, Joaquim; Serna Iglesias, María José
Blesa Aguilera, Maria Josep; Duch Brown, Amalia; Gabarró Vallès, Joaquim; Hernández, Hugo; Serna Iglesias, María José