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 | |
| Source Publication | THEORETICAL COMPUTER SCIENCE
 |
| ISSN | 0304-3975 |
| Volume | 932Pages:69-83 |
| Abstract | 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. |
| Keyword | Mechanism design Facility location Approximation Truthfulness |
| DOI | 10.1016/j.tcs.2022.08.007 |
| Indexed By | SCI |
| Language | 英语 |
| Funding Project | 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 Research Area | Computer Science |
| WOS Subject | Computer Science, Theory & Methods |
| WOS ID | WOS:000888871800007 |
| Publisher | ELSEVIER |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/60547 |
| Collection | 应用数学研究所 |
| Corresponding Author | Wang, Chenhao |
| Affiliation | 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 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment