Fang, Jiazhu and Fang, Qizhi and Liu, Wenjing and Nong, Qingqin and Voudouris, Alexandros A (2025) Mechanism Design with Predictions for Facility Location Games with Candidate Locations. Journal of Combinatorial Optimization, 49 (5). DOI https://doi.org/10.1007/s10878-025-01310-6
Fang, Jiazhu and Fang, Qizhi and Liu, Wenjing and Nong, Qingqin and Voudouris, Alexandros A (2025) Mechanism Design with Predictions for Facility Location Games with Candidate Locations. Journal of Combinatorial Optimization, 49 (5). DOI https://doi.org/10.1007/s10878-025-01310-6
Fang, Jiazhu and Fang, Qizhi and Liu, Wenjing and Nong, Qingqin and Voudouris, Alexandros A (2025) Mechanism Design with Predictions for Facility Location Games with Candidate Locations. Journal of Combinatorial Optimization, 49 (5). DOI https://doi.org/10.1007/s10878-025-01310-6
Abstract
We study mechanism design with predictions in the single (obnoxious) facility location games with candidate locations on the real line, which complements the existing literature on mechanism design with predictions. We first consider the single facility location games with candidate locations, where each agent prefers the facility (e.g., a school) to be located as close to her as possible. We study two social objectives: minimizing the maximum cost and the social cost, and provide deterministic, anonymous, and group strategy-proof mechanisms with predictions that achieve the best possible trade-offs between consistency and robustness, respectively. Additionally, we represent the approximation ratio as a function of the prediction error, indicating that mechanisms can achieve better performance even when predictions are not fully accurate. We also consider the single obnoxious facility location games with candidate locations, where each agent prefers the facility (e.g., a garbage transfer station) to be located as far away from her as possible. For the objective of maximizing the minimum utility, we prove that any strategy-proof mechanism with predictions is unbounded robust. For the objective of maximizing the social utility, we provide a deterministic, anonymous, and group strategy-proof mechanism with prediction that achieves the best possible trade-off between consistency and robustness.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Mechanism design with predictions; Facility location; Candidate locations; Consistency; Robustness |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 27 May 2025 10:09 |
Last Modified: | 28 May 2025 22:08 |
URI: | http://repository.essex.ac.uk/id/eprint/40964 |
Available files
Filename: FL-predictions-accepted.pdf
Embargo Date: 21 May 2026