Speaker: Luciano Gualà, Tor Vergata University
Network creation games (NCG) model the formation of networks in a distributed and noncooperative setting in which selfish nodes strategically choose which links to form. Depending on the model, the game can describe the building of social and communication networks (e.g., P2P, wireless ad-hoc networks, etc.). NCG have been extensively studied, both by economists and computer scientists, due to their versatility in modeling individual-based community formation processes. In this seminar, I first discuss the classic model of Fabrikant et al. [FLMPS'03] for which I will provide the state of the art as far as its computational aspects are concerned (e.g., Price of Anarchy (POA), hardenss of selecting a best-response startegy, etc.). Next, I will present the model introduced in Bilò et al. [BGLP'04] where the generally adopted assumption that players have a common and complete information about the ongoing network is removed. In this model, players have a complete knowledge of the network structure only up to a given radius, which is one of the most qualified local-knowledge models used in distributed computing. I will show that this assumption drastically changes the POA of the game. Finally, I will briefly discuss other models of NCG in order to highlight the current research trends in the area.
[FLMPS'03]: A. Fabrikant, A. Luthra, E. Maneva, C.H. Papadimitriou, S. Shenker, On a network creation game, PODC’03.
[BGLP'16]: D. Bilò, L. Gualà, S. Leucci, G. Proietti, Locality-Based Network Creation Games, Journal of ACM Transactions on Parallel Computing (TOPC), 2016 - Special Issue for SPAA 2014.