10.1007/978-3-319-13129-0_36
Abshoff, Sebastian
Sebastian
Abshoff
Cord-Landwehr, Andreas
Andreas
Cord-Landwehr
Jung, Daniel
Daniel
Jung
Skopalik, Alexander
Alexander
Skopalik
Multilevel Network Games
2014
2017-10-17T12:42:09Z
2019-04-11T14:37:01Z
conference
https://ris.uni-paderborn.de/record/395
https://ris.uni-paderborn.de/record/395.json
161479 bytes
application/pdf
We consider a multilevel network game, where nodes can improvetheir communication costs by connecting to a high-speed network.The n nodes are connected by a static network and each node can decideindividually to become a gateway to the high-speed network. The goalof a node v is to minimize its private costs, i.e., the sum (SUM-game) ormaximum (MAX-game) of communication distances from v to all othernodes plus a fixed price α > 0 if it decides to be a gateway. Between gatewaysthe communication distance is 0, and gateways also improve othernodes’ distances by behaving as shortcuts. For the SUM-game, we showthat for α ≤ n − 1, the price of anarchy is Θ (n/√α) and in this rangeequilibria always exist. In range α ∈ (n−1, n(n−1)) the price of anarchyis Θ(√α), and for α ≥ n(n − 1) it is constant. For the MAX-game, weshow that the price of anarchy is either Θ (1 + n/√α), for α ≥ 1, orelse 1. Given a graph with girth of at least 4α, equilibria always exist.Concerning the dynamics, both games are not potential games. For theSUM-game, we even show that it is not weakly acyclic.