Nash Equilibria in the Facility Location Problem with Externalities

We consider a situation in which the municipal government has to open n cultural centres in a city. The task is to subdivide efficiently the city into n districts Di , and open a centre at the geometric median m(Di) of each district. We assume that the density of the population p in the city is constant p=1. If each inhabitant of district Di living at point x follows the prescriptions of the government and visits the centre m(Di ), his profit is lambda i/area(Di) - d(x,m(Di)) where area(Di) - is the area of Di, that coincides with its population, and lambda i is a positive weight representing the utility of the centre. We show that the government can subdivide the city into a prescribed number of districts so that the optimal strategy of each inhabitant is to visit the centre of his own district. Such a subdivision is called balanced. It turns out that the borders shared by neighbouring districts of a balanced subdivision are pieces of hyperbolae. In order to find a balanced partition we use the potential techniques. Namely, we introduce a functional on all length n partitions that attains it minimum on a balanced partition. The proof of existence of the minimum is quite involved and is attained by a reduction of the continuous problem to a discreet one. The continuous domain is replaced by a discreet subset formed by an e-net and the continuous functional is replaced by a functional defined on partitions of the discreet set. To get back to the continuous case one takes the limit e->0. In the process of the proof we investigate properties of the geometric median of finite subset Se contained in the unit disk. Here the main role is played by A-massive Se sets, i.e, the sets satisfying |Se| > A /e2.