Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game

doi:10.1016/j.ipl.2021.106098

CSpace > 应用数学研究所

	Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game
	Chen, Xujin1,2 ; Hu, Xiaodong1,2 ; Tang, Zhongzheng 3; Wang, Chenhao 4
	2021-06-01
发表期刊	INFORMATION PROCESSING LETTERS
ISSN	0020-0190
卷号	168 页码:6
摘要	We study the two-opposite-facility location game on a line segment, where a mechanism determines the locations of a popular facility and an obnoxious facility for finitely many agents. The agents report their private locations, and try to maximize their own utilities depending on their distances to the facilities. We prove tight bounds on the inapproximability of both randomized and deterministic strategy-proof mechanisms for maximizing the total agent utility minus a penalty determined by the distance between the two facilities. (C) 2021 Elsevier B.V. All rights reserved.
关键词	Facility location game (Universally) strategy-proof mechanism Approximation algorithms Inapproximability
DOI	10.1016/j.ipl.2021.106098
收录类别	SCI
语种	英语
资助项目	MOST of China[2018AAA0101002] ; NNSF of China[11531014] ; Chinese Academy of Sciences[XDA27010102] ; Chinese Academy of Sciences[ZDBS-LY-7008]
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems
WOS记录号	WOS:000624438100006
出版者	ELSEVIER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/58318
专题	应用数学研究所
通讯作者	Wang, Chenhao
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 2.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China 3.Beijing Univ Posts & Telecommun, Sch Sci, Beijing, Peoples R China 4.Univ Nebraska, Dept Comp Sci & Engn, Lincoln, NE 68588 USA
推荐引用方式 GB/T 7714	Chen, Xujin,Hu, Xiaodong,Tang, Zhongzheng,et al. Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game[J]. INFORMATION PROCESSING LETTERS,2021,168:6.
APA	Chen, Xujin,Hu, Xiaodong,Tang, Zhongzheng,&Wang, Chenhao.(2021).Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game.INFORMATION PROCESSING LETTERS,168,6.
MLA	Chen, Xujin,et al."Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game".INFORMATION PROCESSING LETTERS 168(2021):6.