Theory of Computing
-------------------
Title : Near-Optimal Network Design with Selfish Agents
Authors : Elliot Anshelevich, Anirban Dasgupta, Eva Tardos, and Tom Wexler
Volume : 4
Number : 4
Pages : 77-109
URL : http://www.theoryofcomputing.org/articles/v004a004
Abstract
--------
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 + epsilon)-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 + epsilon)-
approximate Nash equilibrium on a network that is close to optimal.