Motivation
Network Creation Games (NCGs) are a well-known approach for explaining and analyzing the structure and quality of real-world networks like the Internet, social networks and transport networks. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. In the last three decades, many strategic models have been proposed and analyzed but most of them are based on strong simplifying assumptions and therefore some of their predictions are not in line with empirical observations from real-world networks. One of the omitted facts is that many important real-world networks are shaped and influenced by an underlying geometry (derived from geographical positions or social distances).
We consider a problem of selfish network creation on an underlying geometric host graph. In these models the constructed network is determined by the agents’ strategies and the focus is on equilibrium networks, where no agent wants to locally change the network. The core research question for such models is to quantify the loss of social welfare due to the lack of a central designer and due to the agents’ selfishness, i.e., comparing the social cost of equilibrium networks with the social optimum network which minimizes the social cost. (See [1] for details about the model.)