Multilevel Network Games
Abshoff, Sebastian
Cord-Landwehr, Andreas
Jung, Daniel
Skopalik, Alexander
ddc:040
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.
2014
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/395
Abshoff S, Cord-Landwehr A, Jung D, Skopalik A. Multilevel Network Games. In: <i>Proceedings of the 10th International Conference on Web and Internet Economics (WINE)</i>. LNCS. ; 2014:435-440. doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_36">10.1007/978-3-319-13129-0_36</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-13129-0_36
info:eu-repo/semantics/closedAccess