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

doi:10.1016/j.ipl.2021.106098

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 应用数学研究所

	Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game
	Chen, Xujin 1,3; Hu, Xiaodong 1,3; Tang, Zhongzheng 4; Wang, Chenhao 2
刊名	INFORMATION PROCESSING LETTERS
	2021-06-01
卷号	168 页码:6
关键词	Facility location game (Universally) strategy-proof mechanism Approximation algorithms Inapproximability
ISSN号	0020-0190
DOI	10.1016/j.ipl.2021.106098
英文摘要	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.
资助项目	MOST of China[2018AAA0101002] ; NNSF of China[11531014] ; Chinese Academy of Sciences[XDA27010102] ; Chinese Academy of Sciences[ZDBS-LY-7008]
WOS研究方向	Computer Science
语种	英语
出版者	ELSEVIER
WOS记录号	WOS:000624438100006
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/58317]
专题	应用数学研究所
通讯作者	Wang, Chenhao
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 2.Univ Nebraska, Dept Comp Sci & Engn, Lincoln, NE 68588 USA 3.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China 4.Beijing Univ Posts & Telecommun, Sch Sci, Beijing, Peoples R China
推荐引用方式 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.