zbMATH — the first resource for mathematics

Network creation games with traceroute-based strategies. (English) Zbl 1318.68124
Halldórsson, Magnús M. (ed.), Structural information and communication complexity. 21st international colloquium, SIROCCO 2014, Takayama, Japan, July 23–25, 2014. Proceedings. Berlin: Springer (ISBN 978-3-319-09619-3/pbk). Lecture Notes in Computer Science 8576, 210-223 (2014).
Summary: 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.
For the entire collection see [Zbl 1292.68004].

68R10 Graph theory (including graph drawing) in computer science
91A10 Noncooperative games
91A43 Games involving graphs
Full Text: DOI