---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sebastian
foaf_name: Abshoff, Sebastian
foaf_surname: Abshoff
- foaf_Person:
foaf_givenName: Andreas
foaf_name: Cord-Landwehr, Andreas
foaf_surname: Cord-Landwehr
- foaf_Person:
foaf_givenName: Daniel
foaf_name: Jung, Daniel
foaf_surname: Jung
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Skopalik, Alexander
foaf_surname: Skopalik
foaf_workInfoHomepage: http://www.librecat.org/personId=40384
bibo_doi: 10.1007/978-3-319-13129-0_36
dct_date: 2014^xs_gYear
dct_language: eng
dct_title: Multilevel Network Games@
...