Leveraging Optimal Transport to Design Optimal Mechanisms for the Facility Location Problem

In this paper, we investigate the k-Facility Location Problem on the line within the Bayesian Mechanism Design framework and analyze the percentile mechanisms, a class of truthful mechanisms that locates the facilities based on the order of the agents’ reports. We irst connect the k-FLP to the Wasserstein projection problems and use this connection to retrieve the limit of the ratio between the expected cost of a percentile mechanism and the expected optimal cost. Moreover, we characterize its limit and convergence speed. We infer an upper bound on the Bayesian approximation ratio when n > k, contrasting the classic worst-case analysis where percentile mechanisms have an unbounded approximation ratio whenever k > 2. This allows us to introduce criteria to determine which percentile mechanism is better suited to address a given agent distribution. We then establish the existence of an optimal percentile mechanism and characterize it via a system of k equations. Finally, we estimate the optimality loss that occurs if we retrieve the optimal percentile mechanism using an approximation of the agents’ distribution. All results hold for the Social, Maximum, and l_p costs.