Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/105473
DC Field | Value | Language |
---|---|---|
dc.contributor | Department of Computing | en_US |
dc.creator | Xu, X | en_US |
dc.creator | Li, B | en_US |
dc.creator | Li, M | en_US |
dc.creator | Duan, L | en_US |
dc.date.accessioned | 2024-04-15T07:34:34Z | - |
dc.date.available | 2024-04-15T07:34:34Z | - |
dc.identifier.issn | 1076-9757 | en_US |
dc.identifier.uri | http://hdl.handle.net/10397/105473 | - |
dc.language.iso | en | en_US |
dc.publisher | A I Access Foundation, Inc | en_US |
dc.rights | © 2021 AI Access Foundation. All rights reserved. | en_US |
dc.rights | All JAIR articles are open access. All articles published on or after May 1, 2023 are available under the terms the Creative Commons CC BY license. All articles published prior to that date (i.e., articles in volumes 1 through 76) are available under the terms of the JAIR License Version 1 (https://www.jair.org/index.php/jair/oldlicense). | en_US |
dc.rights | The following publication Xu, X., Li, B., Li, M., & Duan, L. (2021). Two-facility location games with minimum distance requirement. Journal of Artificial Intelligence Research, 70, 719-756, doi: 10.1613/JAIR.1.12319 is available at https://jair.org/index.php/jair/article/view/12319. | en_US |
dc.title | Two-facility location games with minimum distance requirement | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.identifier.spage | 719 | en_US |
dc.identifier.epage | 756 | en_US |
dc.identifier.volume | 70 | en_US |
dc.identifier.doi | 10.1613/JAIR.1.12319 | en_US |
dcterms.abstract | We study the mechanism design problem of a social planner for locating two facilities on a line interval [0, 1], where a set of n strategic agents report their locations and a mechanism determines the locations of the two facilities. We consider the requirement of a minimum distance 0 ≤ d ≤ 1 between the two facilities. Given the two facilities are heterogeneous, we model the cost/utility of an agent as the sum of his distances to both facilities. In the heterogeneous two-facility location game to minimize the social cost, we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. We also design a strategyproof mechanism minimizing the maximum cost. Given the two facilities are homogeneous, we model the cost/utility of an agent as his distance to the closer facility. In the homogeneous two-facility location game for minimizing the social cost, we show that any deterministic strategyproof mechanism has unbounded approximation ratio. Moreover, in the obnoxious heterogeneous two-facility location game for maximizing the social utility, we propose new deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound (7 − d)/6 for any deterministic strategyproof mechanism. We also design a strategyproof mechanism maximizing the minimum utility. In the obnoxious homogeneous two-facility location game for maximizing the social utility, we propose deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound 4/3. Besides, in the two-facility location game with triple-preference, where each facility may be favorable, obnoxious, indifferent for any agent, we further motivate agents to report both their locations and preferences towards the two facilities truthfully, and design a deterministic group strategyproof mechanism with an approximation ratio 4. | en_US |
dcterms.accessRights | open access | en_US |
dcterms.bibliographicCitation | Journal of artificial intelligence research, 2021, v. 70, p. 719-756 | en_US |
dcterms.isPartOf | Journal of artificial intelligence research | en_US |
dcterms.issued | 2021 | - |
dc.identifier.scopus | 2-s2.0-85102594373 | - |
dc.identifier.eissn | 1943-5037 | en_US |
dc.description.validate | 202402 bcch | en_US |
dc.description.oa | Version of Record | en_US |
dc.identifier.FolderNumber | COMP-0103 | - |
dc.description.fundingSource | Others | en_US |
dc.description.fundingText | Hong Kong Polytechnic University | en_US |
dc.description.pubStatus | Published | en_US |
dc.identifier.OPUS | 50798546 | - |
dc.description.oaCategory | VoR allowed | en_US |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Xu_Two-facility_Location_Games.pdf | 474.75 kB | Adobe PDF | View/Open |
Page views
15
Citations as of Jul 7, 2024
Downloads
4
Citations as of Jul 7, 2024
SCOPUSTM
Citations
22
Citations as of Jul 4, 2024
![](/image/google_scholar.jpg)
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.