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

Results

The results of this Master Project have been published at the 33rd Symposium on Parallelism in Algorithms and Architectures (SPAA 2021).

Friedemann, Wilhelm; Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna; Peters, Jannik; Stephan, Daniel; Vaichenker, Michael Efficiency and Stability in Euclidean Network DesignSymposium on Parallelism in Algorithms and Architectures (SPAA) 2021: 232–242

[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]

Network Design problems typically ask for a minimum cost sub-network from a given host network. This classical point-of-view assumes a central authority enforcing the optimum solution. But how should networks be designed to cope with selfish agents that own parts of the network? In this setting, minimum cost networks may be very unstable in that agents will deviate from a proposed solution if this decreases their individual cost. Hence, designed networks should be both efficient in terms of total cost and stable in terms of the agents' willingness to accept the network. We study this novel type of Network Design problem by investigating the creation of $$(\beta,\gamma)$$-networks, that are in $$\beta$$-approximate Nash equilibrium and have a total cost of at most $$\gamma$$ times the optimal cost, for the recently proposed Euclidean Generalized Network Creation Game by Bilò et al.SPAA2019. There, $$n$$ agents corresponding to points in Euclidean space create costly edges among themselves to optimize their centrality in the created network. Our main result is a simple $$\mathcal{O(n^2)$$-time algorithm that computes a $$(\beta,\beta)$$-network with low $$\beta$$ for any given set of points. Moreover, on integer grid point sets or random point sets our algorithm achieves a low constant $$\beta$$. Besides these results for the Euclidean model, we discuss a generalization of our algorithm to instances with arbitrary, even non-metric, edge lengths. Moreover, in contrast to these algorithmic results, we show that no such positive results are possible when focusing on either optimal networks, i.e., $$(\beta,1)$$-networks, or perfectly stable networks, i.e., $$(1,\gamma)$$-networks, as in both cases NP-hard problems arise, there exist instances with very unstable optimal networks, and there are instances for perfectly stable networks with high total cost. Along the way, we significantly improve several results from Bilò et al. and we asymptotically resolve their conjecture about the Price of Anarchy by providing a tight bound.

@inproceedings{friedemann2021efficiency,
  abstract = {Network Design problems typically ask for a minimum cost sub-network from a given host network. This classical point-of-view assumes a central authority enforcing the optimum solution. But how should networks be designed to cope with selfish agents that own parts of the network? In this setting, minimum cost networks may be very unstable in that agents will deviate from a proposed solution if this decreases their individual cost. Hence, designed networks should be both efficient in terms of total cost and stable in terms of the agents' willingness to accept the network. We study this novel type of Network Design problem by investigating the creation of $(\beta,\gamma)$-networks, that are in $\beta$-approximate Nash equilibrium and have a total cost of at most $\gamma$ times the optimal cost, for the recently proposed Euclidean Generalized Network Creation Game by Bilò et al.SPAA2019. There, $n$ agents corresponding to points in Euclidean space create costly edges among themselves to optimize their centrality in the created network. Our main result is a simple $\mathcal{O}(n^2)$-time algorithm that computes a $(\beta,\beta)$-network with low $\beta$ for any given set of points. Moreover, on integer grid point sets or random point sets our algorithm achieves a low constant $\beta$. Besides these results for the Euclidean model, we discuss a generalization of our algorithm to instances with arbitrary, even non-metric, edge lengths. Moreover, in contrast to these algorithmic results, we show that no such positive results are possible when focusing on either optimal networks, i.e., $(\beta,1)$-networks, or perfectly stable networks, i.e., $(1,\gamma)$-networks, as in both cases NP-hard problems arise, there exist instances with very unstable optimal networks, and there are instances for perfectly stable networks with high total cost. Along the way, we significantly improve several results from Bilò et al. and we asymptotically resolve their conjecture about the Price of Anarchy by providing a tight bound.},
  author = {Friedemann, Wilhelm and Friedrich, Tobias and Gawendowicz, Hans and Lenzner, Pascal and Melnichenko, Anna and Peters, Jannik and Stephan, Daniel and Vaichenker, Michael},
  booktitle = {Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  keywords = {spaa tobiasfriedrich annamelnichenko pascallenzner year2021},
  pages = {232&ndash;242},
  publisher = {ASM},
  title = {Efficiency and Stability in Euclidean Network Design},
  year = 2021
}