Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio

• 成果类型: Article
• 署名作者: Li, Minming; Lu, Pinyan; Sha, Xingchen; Yao, Yuhao; Zhang, Jialin
• 署名单位: City University of Hong Kong; Shanghai University of Finance & Economics; Northwestern University; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Chinese Academy of Sciences; Institute of Computing Technology, CAS
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2026.01.008
• 发表日期: 2026
• 关键词: Location games

摘要

In this paper, we study the two-facility location games with optional preference where the acceptable set of facilities for each agent could be different and an agent's cost is his distance to the closest facility within his acceptable set. The objective is to minimize the total cost of all agents while achieving strategyproofness. For general metrics, we design a deterministic strategyproof mechanism for the problem with an approximation ratio of 1 + 2 alpha, where alpha is the approximation ratio of the offline optimization version. In particular, for the setting on a line, our mechanism root achieves an approximation ratio of 1 + 2, which is tight and improves the previous best upper bound of n/2 + 1 (Chen et al., 2020).