Selfish network creation with non-uniform edge cost

DOI10.1007/978-3-319-66700-3_13MaRDI QIDQ681862zbMATH OpenOpenAlexFDO

Authors Ankit Chauhan, Pascal Lenzner, Anna Melnichenko, Louise Molitor

Publication date 13 February 2018

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

zbMATH Keywords

complexity of computing, constant price of anarchynetwork creation gamesnon-uniform edge costsocial networks

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) Social networks; opinion dynamics (91D30)

Abstract: Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC'03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games. We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has constant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.

Recommendations

• Selfish versus unselfish optimization of network creation
• On selfish creation of robust networks
• Efficient methods for selfish network design
• Efficient Methods for Selfish Network Design
• Near-optimal network design with selfish agents
• Near-optimal network design with selfish agents
• The price of selfish behavior in bilateral network formation
• Costly network formation and regular equilibria
• Computing and Combinatorics

Cited in

(13)

• On the tree conjecture for the network creation game
• Geometric spanner games
• On the tree conjecture for the network creation game
• Selfish versus unselfish optimization of network creation
• Best-response dynamics, playing sequences, and convergence to equilibrium in random games
• An improved bound for the tree conjecture in network creation games
• On tree equilibria in max-distance network creation games
• Geometric Network Creation Games
• The Impact of Cooperation in Bilateral Network Creation
• Fair tree connection games with topology-dependent edge cost
• Network creation games with 2-neighborhood maximization
• One n remains to settle the tree conjecture
• Network creation with homophilic agents

This page was built for publication: Selfish network creation with non-uniform edge cost

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