Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC’03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games. We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has con- stant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.
10/2013–06/2016: Student Assistant at the chair for Efficient Algorithms and Datastructures, Martin-Luther-University Halle-Wittenberg
Since 03/2017: Ph.D. student at the chair for Algorithm Engineering, HPI Potsdam
07/2011: German High School Degree, Elisabeth Gymnasium Halle/Saale
10/2011–11/2014: Bachelor of Science in Computer Science, Martin-Luther-University Halle-Wittenberg, Thesis: "Algorithmen zum Trimmen von Sequenzierungsdaten"
10/2014–01/2017: Master of Science in Computer Science, Martin-Luther-University Halle-Wittenberg, Thesis: "Pfadbasierte Schranken für Mischzeiten von Markov-Ketten mit ganzzahlig linearen Programmen"
Our research focus is on theoretical computer science and algorithm engineering. We are equally interested in the mathematical foundations of algorithms and developing efficient algorithms in practice. A special focus is on random structures and methods.