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 first 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.
Auricchio et al. (Tue,) studied this question.