KMS Of Academy of mathematics and systems sciences, CAS
| Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game | |
Chen, Xujin1,2 ; Hu, Xiaodong1,2; Tang, Zhongzheng3; Wang, Chenhao4
| |
| 2021-06-01 | |
| Source Publication | INFORMATION PROCESSING LETTERS
 |
| ISSN | 0020-0190 |
| Volume | 168Pages:6 |
| Abstract | We study the two-opposite-facility location game on a line segment, where a mechanism determines the locations of a popular facility and an obnoxious facility for finitely many agents. The agents report their private locations, and try to maximize their own utilities depending on their distances to the facilities. We prove tight bounds on the inapproximability of both randomized and deterministic strategy-proof mechanisms for maximizing the total agent utility minus a penalty determined by the distance between the two facilities. (C) 2021 Elsevier B.V. All rights reserved. |
| Keyword | Facility location game (Universally) strategy-proof mechanism Approximation algorithms Inapproximability |
| DOI | 10.1016/j.ipl.2021.106098 |
| Indexed By | SCI |
| Language | 英语 |
| Funding Project | MOST of China[2018AAA0101002] ; NNSF of China[11531014] ; Chinese Academy of Sciences[XDA27010102] ; Chinese Academy of Sciences[ZDBS-LY-7008] |
| WOS Research Area | Computer Science |
| WOS Subject | Computer Science, Information Systems |
| WOS ID | WOS:000624438100006 |
| Publisher | ELSEVIER |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/58318 |
| 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.Beijing Univ Posts & Telecommun, Sch Sci, Beijing, Peoples R China 4.Univ Nebraska, Dept Comp Sci & Engn, Lincoln, NE 68588 USA |
| Recommended Citation GB/T 7714 | Chen, Xujin,Hu, Xiaodong,Tang, Zhongzheng,et al. Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game[J]. INFORMATION PROCESSING LETTERS,2021,168:6. |
| APA | Chen, Xujin,Hu, Xiaodong,Tang, Zhongzheng,&Wang, Chenhao.(2021).Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game.INFORMATION PROCESSING LETTERS,168,6. |
| MLA | Chen, Xujin,et al."Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game".INFORMATION PROCESSING LETTERS 168(2021):6. |
| 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