The max-distance network creation game on general host graphs

DOI10.1007/978-3-642-35311-6_29zbMATH Open1318.68123arXiv1407.0643OpenAlexW1527653494MaRDI QIDQ4915722FDOQ4915722

Authors: D. Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti 

Publication date: 11 April 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: In this paper we study a generalization of the classic emph{network creation game} in the scenario in which the $n$ players sit on a given arbitrary emph{host graph}, which constrains the set of edges a player can activate at a cost of $alphageq0$ each. This finds its motivations in the physical limitations one can have in constructing links in practice, and it has been studied in the past only when the routing cost component of a player is given by the sum of distances to all the other nodes. Here, we focus on another popular routing cost, namely that which takes into account for each player its emph{maximum} distance to any other player. For this version of the game, we first analyze some of its computational and dynamic aspects, and then we address the problem of understanding the structure of associated pure Nash equilibria. In this respect, we show that the corresponding price of anarchy (PoA) is fairly bad, even for several basic classes of host graphs. More precisely, we first exhibit a lower bound of $Omega(sqrtn/(1+alpha))$ for any $alpha=o(n)$. Notice that this implies a counter-intuitive lower bound of $Omega(sqrtn)$ for very small values of $alpha$ (i.e., edges can be activated almost for free). Then, we show that when the host graph is restricted to be either $k$-regular (for any constant $kgeq3$), or a 2-dimensional grid, the PoA is still $Omega(1+minalpha,fracnalpha)$, which is proven to be tight for $alpha=Omega(sqrtn)$. On the positive side, if $alphageqn$, we show the PoA is $O(1)$. Finally, in the case in which the host graph is very sparse (i.e., $|E(H)|=n-1+k$, with $k=O(1)$), we prove that the PoA is $O(1)$, for any $alpha$.

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

Recommendations

• The max-distance network creation game on general host graphs
• The price of anarchy in network creation games is (mostly) constant
• The price of anarchy in cooperative network creation games
• The Price of Anarchy in Network Creation Games Is (Mostly) Constant
• On a network creation game

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Noncooperative games (91A10) Games involving graphs (91A43)

Cited In (4)

• Some results of Maria Serna on strategic games: complexity of equilibria and models
• Geometric Network Creation Games
• The price of anarchy in network creation games is (mostly) constant
• The max-distance network creation game on general host graphs

This page was built for publication: The max-distance network creation game on general host graphs

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