Multilevel network games

DOI10.1007/978-3-319-13129-0_36zbMATH Open1404.91039arXiv1409.5383OpenAlexW200577135MaRDI QIDQ2937006FDOQ2937006

Authors: Sebastian Abshoff, Andreas Cord-Landwehr, Daniel Jung, Alexander Skopalik 

Publication date: 7 January 2015

Published in: Web and Internet Economics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1409.5383

Recommendations

• The Price of Anarchy in Network Creation Games Is (Mostly) Constant
• The price of anarchy in network creation games is (mostly) constant
• On a network creation game
• The price of anarchy in network creation games
• The price of anarchy in network creation games

zbMATH Keywords

network gamesmultilevel networksMAX-gameSUM-game

Mathematics Subject Classification ID

Games involving graphs (91A43)

Cited In (2)

• Network Games with Atomic Players
• Algorithms and Computation

This page was built for publication: Multilevel network games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2937006)