The Facility Location Problem with Aleatory Agents

In this paper, we introduce and study the Facility Location Problem withAleatoryAgents(FLPAA), wherethefacilitycanaccommodate anumberofagents, denotedas𝑛, whichislargerthanthenumberof agentsreportingtheirpreferences, denotedas𝑛𝑟. Thesparecapacity is used by 𝑛𝑢: =𝑛 −𝑛𝑟 aleatory agents distributed according to 𝜇. The goal of FLPAA is to find a location𝑦 that minimises the ex-ante social cost, defined as the expected cost of the 𝑛𝑢 agents sampled from 𝜇 plus the classic social cost incurred by the agents reporting their position. We investigate the mechanism design aspects of the FLPAA under the assumption that the mechanism designer lacks knowledge of the distribution 𝜇 but can query 𝑘 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 mechanism and the cost of the optimal solution on the worst-case input ® 𝑥 and worst-case distribution 𝜇, offering a stringent metric that does not depend on 𝜇. In most cases, the lower bound matches the upper bound, proving that our mechanisms are tight, thus no truthful mechanism can achieve a lower SAR. Lastly, we extend our study to the case in which we must locate two facilities.

Authors

• Gennaro Auricchio University of Padua
• Jie Zhang University of Bath

Keywords

• Algorithmic Game Theory
• Mechanism Design
• Facility Location Problem
• Strong Approximation Ratio