FLIGHT: Facility Location Integrating Generalized, Holistic Theory of Welfare

The Facility Location Problem (FLP) is a well-studied optimization problem with applications in many real-world scenarios. Past literature has explored the solutions from different perspectives to tackle FLPs. These include investigating FLPs under objective functions such as utilitarian, egalitarian, Nash welfare, etc. We propose a unified framework, FLIGHT, to accommodate a broad class of welfare notions. The framework undergoes rigorous theoretical analysis, and we prove some structural properties of the solution to FLP. Additionally, we provide approximation bounds, which (under certain assumptions) provide insight into an interesting fact-as the number of agents arbitrarily increases, the choice of welfare notion is irrelevant. Furthermore, the paper examines a scenario in which the agents are independently and identically distributed (i.i.d.) according to a given probability distribution. In this setting, we derive results concerning the optimal estimator of the welfare and establish an asymptotic result for welfare functions. CCS CONCEPTS • Theory of computation → Algorithmic game theory and mechanism design.