Facility’s Perspective to Fair Facility Location Problems

Abstract

We study the problem faced by a decision maker who wants to locate a set of facilities on a real line and allocate agents/items to the facilities. The items have given locations on the line, and can only be assigned to one of their closest facilities. The facilities are controlled by managers, who have additive utility over the items. An optimal solution that maximizes the (utilitarian or egalitarian) social welfare of the facilities may present a very unbalanced allocation of the items to the facilities and hence be perceived as unfair. In this paper, we are interested in fair allocation among facility managers and consider the well-studied proportionality and envy-freeness fairness notions and their relaxations. We assess the availability, existence, approximability, and the quality (price of fairness) of fair solutions, where the quality measures the system efficiency loss under a fair allocation compared to the one that maximizes the social welfare. Further, we show that one can find a Pareto-optimal solution in polynomial time.