Network creation games have been extensively studied, both by economists and computer scientists, due to their versatility in modeling individual-based community formation processes. These processes, in turn, are the theoretical counterpart of several economics, social, and computational applications on the Internet. In their several variants, these games model the tension of a player between the player’s two antagonistic goals: to be as close as possible to the other players and to activate a cheapest possible set of links. However, the generally adopted assumption is that players have a common and complete information about the ongoing network, which is quite unrealistic in practice. In this article, we consider a more compelling scenario in which players have only limited information about the network in whicy they are embedded. More precisely, we explore the game-theoretic and computational implications of assuming that players have a complete knowledge of the network structure only up to a given radius k, which is one of the most qualified local-knowledge models used in distributed computing. In this respect, we define a suitable equilibrium concept, and we provide a comprehensive set of upper and lower bounds to the price of anarchy for the entire range of values of k and for the two classic variants of the game, namely, those in which a player’s cost—besides the activation cost of the owned links—depends on the maximum/sum of all distances to the other nodes in the network, respectively. These bounds are assessed through an extensive set of experiments.

Locality-Based Network Creation Games

Bilò, Davide;LEUCCI, STEFANO;PROIETTI, GUIDO
2016

Abstract

Network creation games have been extensively studied, both by economists and computer scientists, due to their versatility in modeling individual-based community formation processes. These processes, in turn, are the theoretical counterpart of several economics, social, and computational applications on the Internet. In their several variants, these games model the tension of a player between the player’s two antagonistic goals: to be as close as possible to the other players and to activate a cheapest possible set of links. However, the generally adopted assumption is that players have a common and complete information about the ongoing network, which is quite unrealistic in practice. In this article, we consider a more compelling scenario in which players have only limited information about the network in whicy they are embedded. More precisely, we explore the game-theoretic and computational implications of assuming that players have a complete knowledge of the network structure only up to a given radius k, which is one of the most qualified local-knowledge models used in distributed computing. In this respect, we define a suitable equilibrium concept, and we provide a comprehensive set of upper and lower bounds to the price of anarchy for the entire range of values of k and for the two classic variants of the game, namely, those in which a player’s cost—besides the activation cost of the owned links—depends on the maximum/sum of all distances to the other nodes in the network, respectively. These bounds are assessed through an extensive set of experiments.
File in questo prodotto:
File Dimensione Formato  
revised proofs.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 739.16 kB
Formato Adobe PDF
739.16 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/110754
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? ND
social impact