Facility Location Problems with Capacity Constraints: Two Facilities and Beyond

Facility Location Problems with Capacity Constraints: Two Facilities and Beyond

Gennaro Auricchio, Zihe Wang, Jie Zhang

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 2651-2659. https://doi.org/10.24963/ijcai.2024/293

In this paper, we investigate the Mechanism Design aspects of the m-Capacitated Facility Location Problem (m-CFLP) on a line. We focus on two frameworks. In the first framework, the number of facilities is arbitrary, all facilities have the same capacity, and the number of agents is equal to the total capacity of all facilities. In the second framework, we aim to place two facilities, each with a capacity of at least half of the total agents. For both of these frameworks, we propose truthful mechanisms with bounded approximation ratios with respect to the Social Cost (SC) and the Maximum Cost (MC). When m>2, the result sharply contrasts with the impossibility results known for the classic m-Facility Location Problem, where capacity constraints are not considered. Furthermore, all our mechanisms are optimal with respect to the MC and optimal or nearly optimal with respect to the SC among anonymous mechanisms. For both frameworks, we provide a lower bound on the approximation ratio that any truthful and deterministic mechanism can achieve with respect to the SC and MC.
Keywords:
Game Theory and Economic Paradigms: GTEP: Mechanism design
Agent-based and Multi-agent Systems: MAS: Agent theories and models
Agent-based and Multi-agent Systems: MAS: Coordination and cooperation
Agent-based and Multi-agent Systems: MAS: Resource allocation