KMS Of Academy of mathematics and systems sciences, CAS
Mechanisms for dual-role-facility location games: Truthfulness and approximability | |
Chen, Xujin1,2; Li, Minming3; Wang, Changjun1; Wang, Chenhao4,5; Zhang, Mengqi6; Zhao, Yingchao7 | |
2022-10-06 | |
发表期刊 | THEORETICAL COMPUTER SCIENCE |
ISSN | 0304-3975 |
卷号 | 932页码:69-83 |
摘要 | 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. |
关键词 | Mechanism design Facility location Approximation Truthfulness |
DOI | 10.1016/j.tcs.2022.08.007 |
收录类别 | SCI |
语种 | 英语 |
资助项目 | 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 |
WOS类目 | Computer Science, Theory & Methods |
WOS记录号 | WOS:000888871800007 |
出版者 | ELSEVIER |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.amss.ac.cn/handle/2S8OKBNM/60547 |
专题 | 应用数学研究所 |
通讯作者 | 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.City Univ Hong Kong, Dept Comp Sci, Hong Kong, Peoples R China 4.Beijing Normal Univ, Adv Inst Nat Sci, Zhuhai, Peoples R China 5.BNU HKBU United Int Coll, Zhuhai, Peoples R China 6.Beijing Inst Astronaut Syst Engn, Beijing, 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. |
条目包含的文件 | 条目无相关文件。 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论