我们很高兴地宣布，题为「有容量限制且区间受限之设施选址问题的机制设计」的论文已被第 28 届欧洲人工智能会议（ECAI‑2025）接收，并将于 2025 年 10 月 25–30 日在意大利博洛尼亚发表。
- 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)
论文摘要
本研究从机制设计视角考察有限位置空间内具容量限制的 k-设施选址问题。目标是在有界区间 B=[b_1,b_2]内布置 k个受容量约束的设施，以服务对设施理想位置具有偏好的代理人。我们设计满足策略真实性的（strategyproof）机制，引导代理人如实申报其理想位置，并同时尽量最小化两类成本：
社会成本：所有代理人到其被指派设施距离的总和。
最大成本：单个代理人到其被指派设施的最大距离。
在“等容量且无剩余容量”（所有代理人恰被服务）的情形下，我们提出一个确定性策略真实机制。对任意有界区间（(b_1,b_2)∈R），当 k≥3且 n≥3时，该机制达到的近似比为：社会成本 n-1，最大成本 4。我们进一步给出下界：
对任何“按代理人从左到右排序”类的确定性机制，社会成本近似下界为 3/2。
对任意确定性机制，最大成本近似下界为 2。
当 k<3 时，我们的机制在两类成本上均达到紧（tight）界。
此外，我们还分析两种扩展设定：
(1) 等容量但存在剩余容量；
(2) 无剩余容量且设施容量不必相等。
在这两种设定及任意有界区间下，我们给出随机化策略真实机制，其近似性能为：社会成本 3/2，最大成本 2，适用于任意设施数量。同时，我们证明社会成本下界 5/3、最大成本下界 3/2，从而补足并刻画结果的不可改进性范围。
研究团队成员
香港珠海学院
- 卢葦麟教授，信息科学学系正教授，系主任，质量保证处处长
香港城市大学
- 沙星辰 — 学生, 计算机科学系
- 李闽溟 — 教授, 计算机科学系
内布拉斯加-林肯大学
- Hau Chan — 助理教授, 计算机学院
东南大学
- 周颖豪 — 副教授, 计算机科学与工程学院
香港理工大学
- 方志杰 — 高级讲师, 数据科学及人工智能学系
部分论文照片
