We are pleased to announce that the conference paper titled “Mechanism Design for Facility Location Problems with Capacity Constraints in Bounded Location Space” by Xingchen Sha, Hau Chan, Vincent Chau, Ken C. K. Fong, Minming Li, and Wai Lun Lo has been accepted for presentation at the 28th European Conference on Artificial Intelligence (ECAI-2025)
- Xingchen Sha, Hau Chan, Vincent Chau, Ken C. K. Fong, Minming Li, Wai Lun LO: “Mechanism Design for Facility Location Problems with Capacity Constraints in Bounded Location Space”, ECAI-2025, 28th European Conference on Artificial Intelligence 2025, Bologna, Italy, 25-30 Oct 2025 (Accepted)
Paper Abstract
The k-facility location problem with capacity constraints in bounded location space is studied from the mechanism design perspective. The objective is to locate k capacity-constrained facilities in a bounded interval (i.e., B = [b₁, b₂]) to serve agents who have preferences on the ideal facility locations. Strategyproof mechanisms are designed to elicit agents’ true ideal locations and to locate facilities that minimize the social cost (the sum of agents’ distances to their facilities) and the maximum cost (the largest agent-facility distance).For the equal capacity setting without spare capacity (all agents are served exactly), a deterministic strategyproof mechanism is proposed. For any bounded interval (b₁, b₂ ∈ ℝ), the mechanism achieves approximation ratios of n – 1 for the social cost and 4 for the maximum cost when k ≥ 3 facilities and n ≥ 3 agents. Lower bounds of 3/2 for the social cost (for deterministic mechanisms that order agents from left to right) and 2 for the maximum cost (for any deterministic mechanism) are established. Tight bounds for both costs are achieved when k < 3 facilities.The equal capacity setting with spare capacity and the arbitrary capacity setting without spare capacity are also considered. For these two settings and any bounded interval, randomized strategyproof mechanisms are provided, achieving approximation ratios of 3/2 for the social cost and 2 for the maximum cost with any number of facilities. These results are complemented by lower bounds of 5/3 for the social cost and 3/2 for the maximum cost.
The k-facility location problem with capacity constraints in bounded location space is studied from the mechanism design perspective. The objective is to locate k capacity-constrained facilities in a bounded interval (i.e., B = [b₁, b₂]) to serve agents who have preferences on the ideal facility locations. Strategyproof mechanisms are designed to elicit agents’ true ideal locations and to locate facilities that minimize the social cost (the sum of agents’ distances to their facilities) and the maximum cost (the largest agent-facility distance).For the equal capacity setting without spare capacity (all agents are served exactly), a deterministic strategyproof mechanism is proposed. For any bounded interval (b₁, b₂ ∈ ℝ), the mechanism achieves approximation ratios of n – 1 for the social cost and 4 for the maximum cost when k ≥ 3 facilities and n ≥ 3 agents. Lower bounds of 3/2 for the social cost (for deterministic mechanisms that order agents from left to right) and 2 for the maximum cost (for any deterministic mechanism) are established. Tight bounds for both costs are achieved when k < 3 facilities.The equal capacity setting with spare capacity and the arbitrary capacity setting without spare capacity are also considered. For these two settings and any bounded interval, randomized strategyproof mechanisms are provided, achieving approximation ratios of 3/2 for the social cost and 2 for the maximum cost with any number of facilities. These results are complemented by lower bounds of 5/3 for the social cost and 3/2 for the maximum cost.
The research team members
Hong Kong Chu Hai College
- Wai Lun Lo, Full Professor, Director of Quality Assurance, Head, Department of Computer Science
City University of Hong Kong
- Xingchen Sha — Student, Department of Computer Science
- Minming Lia — Professor, Department of Computer Science
University of Nebraska-Lincoln, USA
- Hau Chan — Assistant Professor, School of Computing
Southeast University
- Vincent Chau — Associate Professor, School of Computer Science and Engineering
The Hong Kong Polytechnic University
- Ken C. K. Fong — Senior Lecturer, Department of Data Science and Artificial Intelligence
Some photos from the paper
