Mechanisms for dual-role-facility location games: Truthfulness and approximability
文献类型：期刊论文
| 作者 | Chen, Xujin2,3 ; Li, Minming4; Wang, Changjun2; Wang, Chenhao5,6; Zhang, Mengqi1; Zhao, Yingchao7
|
| 刊名 | THEORETICAL COMPUTER SCIENCE
 |
| 出版日期 | 2022-10-06 |
| 卷号 | 932页码:69-83 |
| ISSN号 | 0304-3975 |
| 关键词 | Mechanism design Facility location Approximation Truthfulness |
| 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。