On the price of anarchy for high-price links

DOI10.1007/978-3-030-35389-6_23zbMATH Open1435.91034arXiv1909.09799OpenAlexW2991245402MaRDI QIDQ777977FDOQ777977

Carme Àlvarez, Arnau Messegué

Publication date: 30 June 2020

Abstract: We study Nash equilibria and the price of anarchy in the classic model of Network Creation Games introduced by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker in 2003. This is a selfish network creation model where players correspond to nodes in a network and each of them can create links to the other $n-1$ players at a prefixed price $alpha>0$. The player's goal is to minimise the sum of her cost buying edges and her cost for using the resulting network. One of the main conjectures for this model states that the price of anarchy, i.e. the relative cost of the lack of coordination, is constant for all $alpha$. This conjecture has been confirmed for $alpha=O(n^{1-delta})$ with $deltageq1/logn$ and for $alpha>4n-13$. The best known upper bound on the price of anarchy for the remaining range is $2^{O(sqrtlogn)}$. We give new insights into the structure of the Nash equilibria for $alpha>n$ and we enlarge the range of the parameter $alpha$ for which the price of anarchy is constant. Specifically, we prove that for any small $epsilon>0$, the price of anarchy is constant for $alpha>n(1+epsilon)$ by showing that any biconnected component of any non-trivial Nash equilibrium, if it exists, has at most a constant number of nodes.

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

Mathematics Subject Classification ID

Games involving graphs (91A43)

Cites Work

• On a network creation game
• The price of anarchy in network creation games
• On nash equilibria for a network creation game
• The price of anarchy in network creation games is (mostly) constant
• The price of anarchy in network creation games
• On the price of anarchy for high-price links
• On the tree conjecture for the network creation game
• Tree Nash Equilibria in the Network Creation Game

Cited In (12)

• Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy
• Geometric Network Creation Games
• An improved bound for the tree conjecture in network creation games
• On tree equilibria in max-distance network creation games
• Existence of anonymous link tolls for decentralizing an oligopolistic game and the efficiency analysis
• On the price of anarchy for high-price links
• On bipartite sum basic equilibria
• The diameter of sum basic equilibria games
• The Impact of Cooperation in Bilateral Network Creation
• Price of Anarchy in the Link Destruction (Adversary) Model
• Social distancing network creation
• On the tree conjecture for the network creation game

   Recommendations

• Price of Anarchy in the Link Destruction (Adversary) Model 👍 👎
• Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy 👍 👎
• Price of Anarchy in Networks with Heterogeneous Latency Functions 👍 👎
• Price of anarchy for highly congested routing games in parallel networks 👍 👎
• The price of anarchy is independent of the network topology 👍 👎
• The price of anarchy and the design of scalable resource allocation mechanisms 👍 👎
• The Price of Anarchy in Selfish Multicast Routing 👍 👎
• The price of anarchy in an exponential multi-server 👍 👎
• Design of price mechanisms for network resource allocation via price of anarchy 👍 👎
• The price of anarchy for network formation in an adversary model 👍 👎

This page was built for publication: On the price of anarchy for high-price links

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