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.