Near-optimal network design with selfish agents

By Elliot Anshelevich, Anirban Dasgupta, É. Tardos, Tom Wexler. Symposium on the Theory of Computing, 2003

298 citations recorded by the source corpus.

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 as cheap as the optimal network, and give a polynomial time algorithm to find a (1+ε)-approximate Nash equilibrium that does not cost much more. For the general connection game we prove that there is a 3-approximate Nash equilibrium that is as cheap as the optimal network, and give an algorithm to find a (4.65+ε)-approximate Nash equilibrium that does not cost much more.

Subfields: Economics and Econometrics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/eebd08b56a2d35e7482345b2fdb659c32db73338

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Management Science and Operations Research

Citations in the corpus

The price of stability for network design with fair cost allocation (2004, background): “§Cornell University, Department of Computer Science, Upson Hall, Ithaca, NY 14853.”
Network games (2004, background): “Work in price of stability has focused on network design [1, 2] and routing [5, 2].”