Multilevel Network Games

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 $\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 $\alpha \le n-1$, the price of anarchy is $\Theta (n/\sqrt{\alpha })$ and in this range equilibria always exist. In range $\alpha \in (n-1,n(n-1))$ the price of anarchy is $\Theta (\sqrt{\alpha })$, and for $\alpha \ge n(n-1)$ it is constant. For the MAX-game, we show that the price of anarchy is either $\Theta (1+n/\sqrt{\alpha })$, for $\alpha \ge 1$, or else $1$. Given a graph with girth of at least $4\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.

An extended abstract of this paper has been accepted for publication in the proceedings of the 10th International Conference on Web and Internet Economics (WINE)