我們很高興地宣布，題為「有容量限制且區間受限之設施選址問題的機制設計」已獲第 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 — 助理教授，計算機學院
東南大學
- 周穎豪 — 副教授，計算機科學與工程學院
香港理工大學
- 方志傑 — 高級講師，數據科學及人工智能學系
部分論文照片
