Facility location games with optional preference

doi:10.1016/j.tcs.2020.10.004

	Facility location games with optional preference
	Chen, Zhihuai 1,2; Fong, Ken C. K.3; Li, Minming 4; Wang, Kai 4; Yuan, Hongning 4; Zhang, Yong 5
	2020-12-22
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	847 页码:185-197
摘要	In this paper, we study the optional preference model of the facility location game problem with two heterogeneous facilities on a line. The preference of each agent is one of the two facilities or both facilities, and the cost of each agent is a function of the distances to the facilities that the agent prefers. We consider two cost functions: Minimum Distance and Maximum Distance functions. Aiming at minimizing the maximum cost or the social cost of agents, we propose different strategyproof mechanisms without monetary transfers and derive both lower and upper bounds of the approximation ratios with respect to strategyproof mechanisms. In the variant of Minimum Distance, we propose a 2-approximation deterministic strategyproof mechanism for the maximum cost objective, and prove a lower bound of 4/3, while for the social cost objective we propose a (n/2+1)-approximation deterministic strategyproof mechanism and prove a lower bound of 2, also a lower bound of 3/2 for randomized mechanisms. In the variant of Maximum Distance, we propose an optimal deterministic strategyproof mechanism for the maximum cost objective and a 2-approximation deterministic strategyproof mechanism for the social cost objective. (C) 2020 Elsevier B.V. All rights reserved.
关键词	Game theory Facility location game Algorithmic mechanism design Approximation
DOI	10.1016/j.tcs.2020.10.004
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[12071460] ; National Natural Science Foundation of China[61832003] ; National Natural Science Foundation of China[61761136014] ; National Natural Science Foundation of China[61872334] ; 973 Program of China[2016YFB1000201] ; K. C. Wong Education Foundation ; Research Grants Council of the Hong Kong Special Administrative Region, China[11200518] ; NSFC[11771365]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000588118200014
出版者	ELSEVIER
引用统计	被引频次：14[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/16052
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Wang, Kai
作者单位	1.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, 19 A Yuquan Rd, Beijing, Peoples R China 2.Univ Chinese Acad Sci, 6 Kexueyuan South Rd, Beijing, Peoples R China 3.Chu Hai Coll Higher Educ, Dept Comp Sci, Tuen Mun, 80 Castle Peak Rd, Hong Kong, Peoples R China 4.City Univ Hong Kong, Dept Comp Sci, Kowloon Tong, 83 Tat Chee Ave, Hong Kong, Peoples R China 5.Chinese Acad Sci, Shenzhen Inst Adv Technol, 1068 Xueyuan Ave, Shenzhen, Peoples R China
推荐引用方式 GB/T 7714	Chen, Zhihuai,Fong, Ken C. K.,Li, Minming,et al. Facility location games with optional preference[J]. THEORETICAL COMPUTER SCIENCE,2020,847:185-197.
APA	Chen, Zhihuai,Fong, Ken C. K.,Li, Minming,Wang, Kai,Yuan, Hongning,&Zhang, Yong.(2020).Facility location games with optional preference.THEORETICAL COMPUTER SCIENCE,847,185-197.
MLA	Chen, Zhihuai,et al."Facility location games with optional preference".THEORETICAL COMPUTER SCIENCE 847(2020):185-197.