Facility Location Games with Ordinal Preferences
Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45) › 32_Refereed conference paper (with ISBN/ISSN) › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Title of host publication | Computing and Combinatorics |
| Subtitle of host publication | 28th International Conference, COCOON 2022, Shenzhen, China, October 22–24, 2022, Proceedings |
| Editors | Yong Zhang, Dongjing Miao, Rolf Möhring |
| Publisher | Springer |
| Pages | 138-149 |
| ISBN (Electronic) | 978-3-031-22105-7 |
| ISBN (Print) | 9783031221040 |
| Publication status | Published - Jan 2023 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 13595 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Title | 28th International Computing and Combinatorics Conference (COCOON 2022) |
|---|---|
| Location | Shenzhen Institute of Advanced Technology (SIAT), Chinese Academy of Sciences |
| Place | China |
| City | Shenzhen |
| Period | 22 - 24 October 2022 |
Link(s)
Abstract
We consider a new setting of facility location games with ordinal preferences. In such a setting, we have a set of agents and a set of facilities. Each agent is located on a line and has an ordinal preference over the facilities. Our goal is to design strategyproof mechanisms that elicit truthful information (preferences and/or locations) from the agents and locate the facilities to minimize both maximum and total cost objectives as well as to maximize both minimum and total utility objectives. For the four possible objectives, we consider the 2-facility settings in which only preferences are private, or locations are private. For each possible combination of the objectives and settings, we provide lower and upper bounds on the approximation ratios of strategyproof mechanisms, which are asymptotically tight up to a constant. Finally, we discuss the generalization of our results beyond two facilities and when the agents can misreport both locations and preferences. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
Bibliographic Note
Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).
Citation Format(s)
Facility Location Games with Ordinal Preferences. / Chan, Hau; Li, Minming; Wang, Chenhao et al.
Computing and Combinatorics: 28th International Conference, COCOON 2022, Shenzhen, China, October 22–24, 2022, Proceedings. ed. / Yong Zhang; Dongjing Miao; Rolf Möhring. Springer , 2023. p. 138-149 (Lecture Notes in Computer Science; Vol. 13595).Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45) › 32_Refereed conference paper (with ISBN/ISSN) › peer-review
