Multilevel Network Games

Abshoff, Sebastian; Cord-Landwehr, Andreas; Jung, Daniel; Skopalik, Alexander
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.
Research areas:
Type of Publication:
Lecture Notes in Computer Science
Hits: 6800

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information