Springe direkt zu Inhalt

Colloquium by Jannik Peters: Efficiency and Stability in Euclidean Network Design

Dec 14, 2020 | 04:00 PM s.t.

We study the recently proposed Euclidean Generalized Network Creation Game by Bilò et al.[SPAA 2019] and investigate the creation of (beta,gamma)-networks, which are in beta-approximate Nash equilibrium and have a total cost of at most gamma times the optimal cost. In our model we have 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 O(n^2)-time algorithm that computes a (beta,beta)-network with low beta for any given set of points. Along the way, we significantly improve several results from Bilò et al. and we asymptotically resolve a conjecture about the Price of Anarchy.

Time & Location

Dec 14, 2020 | 04:00 PM s.t.


Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)