Network creation games have been extensively studied, both from economists and computer scientists, due to their versatility in modeling individual-based community formation processes, which in turn are the theoretical counterpart of several economics, social, and computational applications on the Internet. 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 paper, we consider a more compelling scenario in which players have only limited information about the network they are embedded in. More precisely, we explore the game theoretic and computational implications of assuming that players have a view of the network restricted to their k-neighborhood, which is one of the most qualified ,local-knowledge models used in distributed computing. To 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.

Locality-based network creation game / Bilò, Davide; Gualà, Luciano; Leucci, Stefano; Proietti, Guido. - (2014), pp. 277-286. ((Intervento presentato al convegno 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'14) tenutosi a Czech Republic nel June 2014 [10.1145/2612669.2612680].

Locality-based network creation game

BILÒ, Davide;
2014

Abstract

Network creation games have been extensively studied, both from economists and computer scientists, due to their versatility in modeling individual-based community formation processes, which in turn are the theoretical counterpart of several economics, social, and computational applications on the Internet. 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 paper, we consider a more compelling scenario in which players have only limited information about the network they are embedded in. More precisely, we explore the game theoretic and computational implications of assuming that players have a view of the network restricted to their k-neighborhood, which is one of the most qualified ,local-knowledge models used in distributed computing. To 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.
978-1-4503-2821-0
Locality-based network creation game / Bilò, Davide; Gualà, Luciano; Leucci, Stefano; Proietti, Guido. - (2014), pp. 277-286. ((Intervento presentato al convegno 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'14) tenutosi a Czech Republic nel June 2014 [10.1145/2612669.2612680].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: https://hdl.handle.net/11388/50506
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 9
social impact