Selfish Creation of Efficient Geometric Networks

Master Project - Summer 2020

Supervisors: Prof. Dr. Tobias Friedrich, Dr. Pascal Lenzner, Anna Melnichenko

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.)

^{Illustration of the strategic edge purchase decision of agents.}

One approach is to consider a bi-criteria optimization problem for finding networks that have low total cost but at the same time are close to an equilibrium. For this we consider \((\beta,\gamma)\)-networks, which are networks having a social cost which is at most a factor of \(\beta\) larger than the minimum possible social cost and where no agent has a strategy change which improves on its individual current cost by more than a factor of \(\gamma\).

Goal

The goal of this project is to analyze the correlation between equilibrium networks and social optimum networks of various versions of NCGs with underlying geometry and to precisely map the Pareto frontier of all \((\beta,\gamma)\)-networks, which is the set of all \((\beta,\gamma)\)-networks such that the vector \((\beta,\gamma)\) is not dominated by some other vector \((\beta',\gamma')\). See the following illustration for examples:

^{Examples of Pareto-optimal networks for the same instance with points in the Euclidean plane. Left: The social optimum network. Middle: A network generated via iterated improvements starting from a MST. Right: A network in Nash equilibrium. From left to right the social cost increases while the networks become more and more stable.}

We want to develop and analyze efficient algorithms for finding networks which lie on the Pareto frontier or which are close to it.

Another interesting approach is to design cost-sharing schemes for stabilizing the minimum cost networks of such geometric models, i.e., distributing the cost of the optimum network such that the network is in \(\gamma\)-approximate equilibrium for \(\gamma\) as close as possible to \(1\). In both approaches it will be vital to exploit properties of the underlying geometry.

What we expect from you. You should bring the curiosity and willingness to delve into an interesting research topic in Algorithmic Game Theory, Computational Geometry and Graph Theory.

What you can expect from us. We will gently introduce you to the field and accompany you all along this interesting journey. This will be a team effort, and we aim at publishing our results at a renowned international conference.

[1]	Davide Bilò, Tobias Friedrich, Pascal Lenzner, Anna Melnichenko: Geometric Network Creation Games. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019. https://arxiv.org/abs/1904.07001