Multilevel Network Games

Sebastian Abshoff*, Andreas Cord-Landwehr, Daniel Jung, Alexander Skopalik

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
16 Downloads (Pure)


We consider a multilevel network game, where nodes can improve their communication costs by connecting to a high-speed network. The n nodes are connected by a static network and each node can decide individually to become a gateway to the high-speed network. The goal of a node v is to minimize its private costs, i.e., the sum (SUM-game) or maximum (MAX-game) of communication distances from v to all other nodes plus a fixed price α > 0 if it decides to be a gateway. Between gateways the communication distance is 0, and gateways also improve other nodes’ distances by behaving as shortcuts. For the SUM-game, we show that for α ≤ n - 1, the price of anarchy is (Formula Presented.) and in this range equilibria always exist. In range α ∈ (n-1, n(n-1)) the price of anarchy is Θ(√ α), and for α ≥ n(n - 1) it is constant. For the MAX-game, we show that the price of anarchy is either Θ (1 + n/ √ α), for α ≥ 1, or else 1. Given a graph with girth of at least 4α, equilibria always exist. Concerning the dynamics, both games are not potential games. For the SUM-game, we even show that it is not weakly acyclic.

Original languageEnglish
Title of host publicationWeb and Internet Economics
Subtitle of host publication10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings
EditorsTie-Yan Liu, Qi Qi, Yinyu Ye
Number of pages6
ISBN (Electronic)978-3-319-13129-0
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event10th Conference on Web and Internet Economics, WINE 2014 - Beijing, China
Duration: 14 Dec 201417 Dec 2014
Conference number: 10

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743


Conference10th Conference on Web and Internet Economics, WINE 2014
Abbreviated titleWINE


Dive into the research topics of 'Multilevel Network Games'. Together they form a unique fingerprint.

Cite this