Mechanisms for dual-role-facility location games: Truthfulness and approximability

doi:10.1016/j.tcs.2022.08.007

	Mechanisms for dual-role-facility location games: Truthfulness and approximability
	Chen, Xujin 2,3; Li, Minming 4; Wang, Changjun 2; Wang, Chenhao 5,6; Zhang, Mengqi 1; Zhao, Yingchao 7
刊名	THEORETICAL COMPUTER SCIENCE
	2022-10-06
卷号	932 页码:69-83
关键词	Mechanism design Facility location Approximation Truthfulness
ISSN号	0304-3975
DOI	10.1016/j.tcs.2022.08.007
英文摘要	This paper studies the dual-role-facility location game with generalized service costs, in which every agent plays a dual role of facility and customer, and is associated with a facility opening cost as his private information. The agents strategically report their opening costs to a mechanism which maps the reports to a set of selected agents and payments to them. Each selected agent opens his facility, incurs his opening cost and receives the payment the mechanism sets for him. Each unselected agent incurs a services cost that is determined by the set of selected agents in a very general way. The mechanism is truthful if under it no agent has an incentive to misreport. We provide a necessary and sufficient condition for mechanisms of the game to be truthful. This characterization particularly requires an invariant service cost for each unselected agent, which is a remarkable difference from related work in literature. As applications of this truthfulness characterization, we focus on the classic metric-space setting, in which agents' service costs equal their distances to closest open facilities. We present truthful mechanisms that minimize or approximately minimize the maximum cost among all agents and the total cost of all agents, respectively. Moreover, when the total payment cannot exceed a given budget, we prove, for both cost-minimization objectives, lower and upper bounds on approximation ratios of truthful mechanisms that satisfy the budget constraint. (c) 2022 Elsevier B.V. All rights reserved.
资助项目	MOST of China[2018AAA0101002] ; CAS[XDA27000000] ; CAS[ZDBS-LY-7008] ; Research Grants Council of Hong Kong[11205619] ; National Natural Science Foundation of China (NSFC)[11971046] ; Artificial Intelligence and Data Science Research Hub, BNU-HKBU UIC[2020KSYS007] ; Artificial Intelligence and Data Science Research Hub, BNU-HKBU UIC[UICR0400025-21] ; Artificial Intelligence and Data Science Research Hub, BNU-HKBU UIC[UICR0700036-22]
WOS研究方向	Computer Science
语种	英语
出版者	ELSEVIER
WOS记录号	WOS:000888871800007
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/60546]
专题	中国科学院数学与系统科学研究院
通讯作者	Wang, Chenhao
作者单位	1.Beijing Inst Astronaut Syst Engn, Beijing, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 3.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China 4.City Univ Hong Kong, Dept Comp Sci, Hong Kong, Peoples R China 5.Beijing Normal Univ, Adv Inst Nat Sci, Zhuhai, Peoples R China 6.BNU HKBU United Int Coll, Zhuhai, Peoples R China 7.Caritas Inst Higher Educ, Hong Kong, Peoples R China
推荐引用方式 GB/T 7714	Chen, Xujin,Li, Minming,Wang, Changjun,et al. Mechanisms for dual-role-facility location games: Truthfulness and approximability[J]. THEORETICAL COMPUTER SCIENCE,2022,932:69-83.
APA	Chen, Xujin,Li, Minming,Wang, Changjun,Wang, Chenhao,Zhang, Mengqi,&Zhao, Yingchao.(2022).Mechanisms for dual-role-facility location games: Truthfulness and approximability.THEORETICAL COMPUTER SCIENCE,932,69-83.
MLA	Chen, Xujin,et al."Mechanisms for dual-role-facility location games: Truthfulness and approximability".THEORETICAL COMPUTER SCIENCE 932(2022):69-83.