The Internet, which is undoubtedly one of the biggest human artifacts built in the last few years, has
been built essentially in an anarchic manner by a large multitude of agents with varying interests and
varying end-goals in mind. It is for this reason that methodology from game theory is most appropriate
for analyzing problems and issues arising with the Internet. A very useful concept in this respect has
been the price of anarchy -- a bound on the cost incurred by selfish agents in accomplishing a goal in
relation to the optimal cost (incurred by a centralized authority).

We will consider a network service provider game that is natural in the context of the Internet and
raise the question of bounding its price of anarchy. Our answer is obtained in two steps. In the first
step, we show that the price of anarchy of this game is precisely the locality gap of the k-facility
location problem under a certain neighborhood structure. The locality gap of a problem is the maximum
ratio of a local optimal solution and a global optimal solution for this problem. Our second step is to
show that the locality gap of the k-facility location problem is at most 5. The latter result is of
independent interest. Additionally, the technique introduced in the first step may help reduce the
question of bounding the price of anarchy for other games to the question of bounding the locality gap
for the corresponding optimization question.