Volume 4 (2008) Article 4 pp. 77-109

Near-Optimal Network Design with Selfish Agents

by Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, and Tom Wexler

Received: September 26, 2007
Published: August 4, 2008
DOI: 10.4086/toc.2008.v004a004

Download article from ToC site:
[PS (5423K)]    [PS.GZ (2322K)]    [PS.ZIP (2322K)]
[PDF (2254K)]    [DVI (249K)]    [ZIP (4253K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: game theory, network design, Nash equilibrium, connection game, price of stability
Categories: electronic commerce, game theory, networks
ACM Classification: G.2.2, F.2.2, F.2.3, J.4
AMS Classification: 68W25, 68W40, 05C85, 90B10, 90B18, 91A43, 91A40

Abstract: [Plain Text Version]

We introduce a simple network design game that models how independent selfish agents can build or maintain a large network. In our game every agent has a specific connectivity requirement, i.e. each agent has a set of terminals and wants to build a network in which his terminals are connected. Possible edges in the network have costs and each agent's goal is to pay as little as possible. Determining whether or not a Nash equilibrium exists in this game is NP-complete. However, when the goal of each player is to connect a terminal to a common source, we prove that there is a Nash equilibrium on the optimal network, and give a polynomial time algorithm to find a (1 + ε)-approximate Nash equilibrium on a nearly optimal network. Similarly, for the general connection game we prove that there is a 3-approximate Nash equilibrium on the optimal network, and give an algorithm to find a (4.65 + ε)-approximate Nash equilibrium on a network that is close to optimal.