Network creation games model the autonomous formation of an interconnected system of selfish users. In particular, when the network will serve as a digital communication infrastructure, each user is identified by a node of the network, and contributes to the build-up process by strategically balancing between her building cost (i.e., the number of links she personally activates in the network) and her usage cost (i.e., some function of the distance in the sought network to the other players). When the corresponding game is analyzed, the generally adopted assumption is that players have a common and complete information about the evolving network topology, which is quite unrealistic though, due to the massive size this may have in practice. In this paper, we thus relax this assumption, by instead letting the players have only a partial knowledge of the network. To this respect, we make use of three popular traceroute-based knowledge models used in network discovering (i.e., the activity of reconstructing the topology of an unknown network through queries at its nodes), namely: (i) distance vector, (ii) shortest-path tree view, and (iii) layered view. For all these models, we provide exhaustive answers to the canonical algorithmic game theoretic questions: convergence, computational complexity for a player of selecting a best response, and tight bounds to the price of anarchy, all of them computed w.r.t. a suitable (and unifying) equilibrium concept.

Network Creation Games with Traceroute-Based Strategies

D. Bilò;S. Leucci;PROIETTI, GUIDO
2014

Abstract

Network creation games model the autonomous formation of an interconnected system of selfish users. In particular, when the network will serve as a digital communication infrastructure, each user is identified by a node of the network, and contributes to the build-up process by strategically balancing between her building cost (i.e., the number of links she personally activates in the network) and her usage cost (i.e., some function of the distance in the sought network to the other players). When the corresponding game is analyzed, the generally adopted assumption is that players have a common and complete information about the evolving network topology, which is quite unrealistic though, due to the massive size this may have in practice. In this paper, we thus relax this assumption, by instead letting the players have only a partial knowledge of the network. To this respect, we make use of three popular traceroute-based knowledge models used in network discovering (i.e., the activity of reconstructing the topology of an unknown network through queries at its nodes), namely: (i) distance vector, (ii) shortest-path tree view, and (iii) layered view. For all these models, we provide exhaustive answers to the canonical algorithmic game theoretic questions: convergence, computational complexity for a player of selecting a best response, and tight bounds to the price of anarchy, all of them computed w.r.t. a suitable (and unifying) equilibrium concept.
978-3-319-09619-3
File in questo prodotto:
File Dimensione Formato  
c50 SIROCCO 2014.pdf

non disponibili

Licenza: Non specificato
Dimensione 277.26 kB
Formato Adobe PDF
277.26 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/37203
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 8
social impact