TY - GEN
T1 - Facility Location Games with Ordinal Preferences
AU - Chan, Hau
AU - Li, Minming
AU - Wang, Chenhao
AU - Zhao, Yingchao
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85147997674
U2 - 10.1007/978-3-031-22105-7_13
DO - 10.1007/978-3-031-22105-7_13
M3 - 会议稿件
AN - SCOPUS:85147997674
SN - 9783031221040
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 138
EP - 149
BT - Computing and Combinatorics - 28th International Conference, COCOON 2022, Proceedings
A2 - Zhang, Yong
A2 - Miao, Dongjing
A2 - Möhring, Rolf
PB - Springer Science and Business Media Deutschland GmbH
T2 - 28th International Conference on Computing and Combinatorics, COCOON 2022
Y2 - 22 October 2022 through 24 October 2022
ER -