@article{abshoff2014multilevel,
author = "Sebastian Abshoff and Andreas Cord-Landwehr and Daniel Jung and Alexander Skopalik",
abstract = "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 \$\backslash alpha > 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 \$\backslash alpha \backslash leq n-1\$, the price of anarchy is \$\backslash Theta(n/\backslash sqrt\{\backslash alpha\})\$ and in this range equilibria always exist. In range \$\backslash alpha \backslash in (n-1,n(n-1))\$ the price of anarchy is \$\backslash Theta(\backslash sqrt\{\backslash alpha\})\$, and for \$\backslash alpha \backslash geq n(n-1)\$ it is constant. For the MAX-game, we show that the price of anarchy is either \$\backslash Theta(1 + n/\backslash sqrt\{\backslash alpha\})\$, for \$\backslash alpha\backslash geq 1\$, or else \$1\$. Given a graph with girth of at least \$4\backslash alpha\$, equilibria always exist. Concerning the dynamics, both the SUM-game and the MAX-game are not potential games. For the SUM-game, we even show that it is not weakly acyclic.",
journal = "Lecture Notes in Computer Science",
pages = "435--440",
title = "{M}ultilevel {N}etwork {G}ames",
url = "http://arxiv.org/abs/1409.5383",
volume = "8877",
year = "2014",
}