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 : https://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.