The Impact of Cooperation in Bilateral Network Creation

DOI10.1145/3583668.3594588arXiv2207.03798OpenAlexW4380874184MaRDI QIDQ6202269FDOQ6202269

Author name not available (Why is that?), Pascal Lenzner, Hans Gawendowicz, Tobias Friedrich

Publication date: 26 March 2024

Published in: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: Many real-world networks, like the Internet, are not the result of central design but instead the outcome of the interaction of local agents who are selfishly optimizing for their individual utility. The famous Network Creation Game [Fabrikant et al., PODC 2003] enables us to understand such processes, their dynamics, and their outcomes in the form of equilibrium states. In this model, agents buy incident edges towards other agents for a price of $alpha$ and simultaneously try to minimize their buying cost and their total hop distance. Since in many real-world networks, e.g., social networks, consent from both sides is required to maintain a connection, Corbo and Parkes [PODC 2005] proposed a bilateral version of the Network Creation Game, in which mutual consent and payment are required in order to create edges. It is known that the bilateral version has a significantly higher Price of Anarchy, compared to the unilateral version. This is counter-intuitive, since cooperation should help to avoid socially bad states. We investigate this phenomenon by analyzing the Price of Anarchy of the bilateral version with respect to different solution concepts that allow for various degrees of cooperation among the agents. With this, we provide insights into what kind of cooperation is needed to ensure that socially good networks are created. We present a collection of asymptotically tight bounds on the Price of Anarchy that precisely map the impact of cooperation on the quality of tree networks and we find that weak forms of cooperation already yield a significantly improved Price of Anarchy. Moreover, for general networks we show that enhanced cooperation yields close to optimal networks for a wide range of edge prices.

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

zbMATH Keywords

cooperationprice of anarchynetwork creation games

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• A strategic model of social and economic networks
• Worst-case equilibria
• Strong price of anarchy
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• On a network creation game
• Network Creation Games: Think Global – Act Local
• The price of anarchy in network creation games
• A Bounded Budget Network Creation Game
• The price of selfish behavior in bilateral network formation
• Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games
• The price of anarchy in network creation games is (mostly) constant
• On the History of the Minimum Spanning Tree Problem
• On the topologies formed by selfish peers
• On the price of anarchy for high-price links
• On Selfish Creation of Robust Networks
• Selfish network creation with non-uniform edge cost
• On the tree conjecture for the network creation game
• Tree Nash Equilibria in the Network Creation Game
• Quality of Service in Network Creation Games

This page was built for publication: The Impact of Cooperation in Bilateral Network Creation

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