Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio

doi:10.1016/j.geb.2026.01.008

CSpace

	Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio
	Li, Minming 1; Lu, Pinyan 2,3; Sha, Xingchen 1,4; Yao, Yuhao 5; Zhang, Jialin 5,6
	2026-03-01
发表期刊	GAMES AND ECONOMIC BEHAVIOR
ISSN	0899-8256
卷号	157 页码:125-137
摘要	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).
关键词	Algorithmic game theory Facility location Computational social choice
DOI	10.1016/j.geb.2026.01.008
收录类别	SCI
语种	英语
WOS研究方向	Business & Economics
WOS类目	Economics
WOS记录号	WOS:001683156300001
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/42788
专题	中国科学院计算技术研究所
通讯作者	Sha, Xingchen
作者单位	1.City Univ Hong Kong, Hong Kong, Peoples R China 2.Shanghai Univ Finance & Econ, Shanghai, Peoples R China 3.Minist Educ, Key Lab Interdisciplinary Res Computat & Econ SUFE, Shanghai, Peoples R China 4.Northwestern Univ, Evanston, IL 60208 USA 5.Univ Chinese Acad Sci, Beijing, Peoples R China 6.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Li, Minming,Lu, Pinyan,Sha, Xingchen,et al. Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio[J]. GAMES AND ECONOMIC BEHAVIOR,2026,157:125-137.
APA	Li, Minming,Lu, Pinyan,Sha, Xingchen,Yao, Yuhao,&Zhang, Jialin.(2026).Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio.GAMES AND ECONOMIC BEHAVIOR,157,125-137.
MLA	Li, Minming,et al."Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio".GAMES AND ECONOMIC BEHAVIOR 157(2026):125-137.