Selfish Network Creation: Structure & Locality

21^st July 2015, 13:00 Ashton Lecture Theater
Dr Pascal Lenzner
Department of Computer Science
Friedrich-Schiller-University Jena
Germany

Abstract

Network Creation Games model the construction of a communication network by selfish agents without any external coordination. These games became popular as a means to study the structure of complex networks like the Internet or social networks. Agents of the game are nodes in a network which can buy incident edges to connect to other nodes. Each agent tries to occupy a central position in the network at minimum cost for building edges. Recent research has shed light on some structural properties of equilibrium networks of these games. However, despite all these efforts there are still many intriguing open problems left - most prominently settling the Price of Anarchy. In my talk I will present new structural insights which open up a new line of attack on the Price of Anarchy question.

In the second part of my talk, I will survey recent results on locality in Network Creation Games. The original model assumes that any node may buy a link to any other node in the network, independently of their position. Especially for modelling large communication or social networks, this assumption is hard to justify since no agent may have complete knowledge of the network structure. Very recently this observation has led to an analysis of several variants where agents only have local knowledge of the network and are therefore restricted to act locally. The natural next step in this line of research is to allow agents to probe and evaluate different local strategies and then choose the most profitable one of them. For this more optimistic locality model I will present results on the impact on the agents' cost, the game dynamics and on the resulting equilibrium networks.