Facility location games with optional preference
文献类型：期刊论文
| 作者 | Chen, Zhihuai1,2; Fong, Ken C. K.3; Li, Minming4; Wang, Kai4; Yuan, Hongning4; Zhang, Yong5 |
| 刊名 | THEORETICAL COMPUTER SCIENCE
 |
| 出版日期 | 2020-12-22 |
| 卷号 | 847页码:185-197 |
| 关键词 | Game theory Facility location game Algorithmic mechanism design Approximation |
| ISSN号 | 0304-3975 |
| DOI | 10.1016/j.tcs.2020.10.004 |
| 英文摘要 | 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. |
| 资助项目 | 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记录号 | WOS:000588118200014 |
| 出版者 | ELSEVIER |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/16051]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。