Designing Optimal Mechanisms to Locate Facilities with Insufficient Capacity for Bayesian Agents - Auricchio, Gennaro; Zhang, Jie (Proceedings of the AAAI Conference on Artificial Intelligence, 2026)
In this paper, we study the Facility Location Problem with Scarce Resources (FLPSR) under the assumption that agents’ type follows a probability distribution on [0,1]. In the FLPSR, the goal is to identify the optimal locations for one or more capacitated facilities to maximize Social Welfare (SW), defined as the sum of the utilities of all agents. Since the total capacity of the facilities is insufficient to serve all agents, they compete in a First-Come-First-Served game to get accommodated. The main contribution of the paper ties Optimal Transport theory to the problem of selecting a truthful mechanism tailored to the agents’ distributions. For the case of a single facility, we show that an optimal mechanism always exists. We examine three classes of probability distributions and characterize the optimal mechanism analytically or provide a routine to numerically compute it. We extend our results to the case in which we have two capacitated facilities to place. Initially, we assume that agents are independent and identically distributed, but our techniques generalize to scenarios where agents are not identically distributed. Finally, we validate our findings through several numerical experiments, including: (i) deriving optimal mechanisms for the class of beta distributions, (ii) assessing the Bayesian approximation ratio of these mechanisms for small numbers of agents, and (iii)assessing how quickly the expected mechanism SW converges to its limit.