2024/09/27 by Auricchio, Gennaro, Zhang, Jie
#91A68 68W25 #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Multiagent Systems (cs.MA)
paper · doi:10.48550/arxiv.2409.18817
In this paper, we introduce and study the Facility Location Problem with Aleatory Agents (FLPAA), where the facility accommodates n agents larger than the number of agents reporting their preferences, namely nr. The spare capacity is used by nu=n-nr aleatory agents sampled from a probability distribution μ. The goal of FLPAA is to find a location that minimizes the ex-ante social cost, which is the expected cost of the nu agents sampled from μplus the cost incurred by the agents reporting their position. We investigate the mechanism design aspects of the FLPAA under the assumption that the Mechanism Designer (MD) lacks knowledge of the distribution μ but can query k quantiles of μ. We explore the trade-off between acquiring more insights into the probability distribution and designing a better-performing mechanism, which we describe through the strong approximation ratio (SAR). The SAR of a mechanism measures the highest ratio between the cost of the mechanisms and the cost of the optimal solution on the worst-case input x and worst-case distribution μ, offering a metric for efficiency that does not depend on μ. We divide our study into four different information settings: the zero information case, in which the MD has access to no quantiles; the median information case, in which the MD has access to the median of μ; the nu-quantile information case, in which the MD has access to nu quantiles of its choice, and the k-quantile information case, in which the MD has access to k