Abstract
We study deterministic mechanism design for constrained heterogeneous two-facility location games. The constraint here means that the feasible locations of facilities are specified and the number of facilities that can be built at each feasible location is limited. Given that a set of agents can strategically report their locations on the real line, the authority wants to design strategyproof mechanisms (i.e., mechanisms that can incentivize agents to report truthful private information) to construct two heterogeneous facilities under constraint, while optimizing the corresponding social objectives. Assuming that each agent’s individual objective depends on the sum of her distance to facilities, we consider locating desirable and obnoxious facilities respectively. For the former, we give a deterministic group strategyproof mechanism, which guarantees 3-approximation under the objectives of minimizing the sum cost and the maximum cost. We show that no deterministic strategyproof mechanism can have an approximation ratio of less than 2 under the sum/maximum cost objective. For the latter, we give a deterministic group strategyproof mechanism with 2-approximation under the objectives of maximizing the sum utility and the minimum utility. We show that no deterministic strategyproof mechanism can have an approximation ratio of less than 3/2 under the sum utility objective and 2 under the minimum utility objective, respectively.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data availability
None.
Notes
Here, we assume that each agent wants the sum of her distance to the two obnoxious facilities to be as large as possible and apply the sum-variant utility. If each agent prefers the nearest obnoxious facility to stay away from her as possible, it should be better to regard the distance from her to the nearest facility as her utility (referred to as min-variant).
While our paper is being reviewed, the results have been improved by Kanellopoulos et al. (2023) to a matching bound under the sum/maximum cost objective.
Although there always exists an optimal solution in \(\{(a_1,a_2),(a_{m-1},a_m),(a_1,a_m)\}\), the approximation ratio of locating at \((a_{1}, a_{2})\) or \((a_{m-1}, a_{m})\) is unbounded due to some extreme instances. This inspires us to propose LR-Point Mechanism.
References
Cai Q, Filos-Ratsikas A, Tang P (2016) Facility location with minimax envy. In: Proceedings of the 25th international joint conference on artificial intelligence, pp 137–143
Chan, H., Filos-Ratsikas, A., Li, B., Li, M., Wang, C (2021) Mechanism design for facility location problems: a survey. In: Proceedings of the thirtieth international joint conference on artificial intelligence (IJCAI), pp 4356–4365. https://doi.org/10.24963/ijcai.2021/596
Chen X, Hu X, Tang Z, Wang C (2021) Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game. J Inf Process Lett 168:106098
Chen X, Fang Q, Liu W, Ding Y, Nong Q (2022) Strategyproof mechanisms for 2-facility location games with minimax envy. J Comb Optim 43:1628–1644. https://doi.org/10.1007/s10878-021-00711-7
Cheng Y, Yu W, Zhang G (2013) Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoret Comput Sci 497:154–163. https://doi.org/10.1016/j.tcs.2011.11.041
Ding Y, Liu W, Chen X, Fang Q, Nong Q (2020) Facility location game with envy ratio. Comput Ind Eng 148(3):106710. https://doi.org/10.1016/j.cie.2020.106710
Dokow E, Feldman M, Meir R, Nehama I (2012) Mechanism design on discrete lines and cycles. In: Proceedings of the 13rd ACM conference on electronic commerce, pp 423–440. https://doi.org/10.1145/2229012.2229045
Feigenbaum I, Sethuraman J (2015) Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location models. models. In: AAAI workshop: incentive and trust in Ecommunities
Feldman M, Fiat A, Golomb I (2016) On voting and facility location. In: Proceedings of the 2016 ACM conference on economics and computation, pp 269–286. https://doi.org/10.1145/2940716.2940725
Fong CKK, Li M, Lu P, Todo T, Yokoo c,M (2020) Facility location games with fractional preferences. In: Proceedings of the AAAI conference on artificial intelligence, vol 32, no. 1. https://doi.org/10.1609/aaai.v32i1.11458
Gai L, Liang M, Wang C (2022) Obnoxious facility location games with candidate locations. In: AAIM 2022, LNCS 13513. Springer, Cham
Kanellopoulos P, Voudouris A A, Zhang R (2023) Truthful two-facility location with candidate locations. In: SAGT 2023, LNCS 14238, pp 365–382. https://doi.org/10.1007/978-3-031-43254-5_21
Liu W, Ding Y, Chen X, Fang Q, Nong Q (2021) Multiple facility location games with envy ratio. Theoret Comput Sci 864:1–9. https://doi.org/10.1016/j.tcs.2021.01.016
Lu P, Wang Y, Zhou Y (2009) Tighter bounds for facility games. In: Proceedings of the 5th international workshop on internet and network economics, pp 137–148. https://doi.org/10.1007/978-3-642-10841-9
Lu P, Sun X, Wang Y, Zhu ZA (2010) Asymptotically optimal strategy-proof mechanisms for two-facility games. In: Proceedings of the 11th ACM conference on electronic commerce, pp 315–324. https://doi.org/10.1145/1807342.1807393
Moulin H (1980) On strategy-proofness and single peakedness. Public Choice 35(4):437–455. https://doi.org/10.1007/BF00128122
Procaccia AD, Tennenholtz M (2009) Approximate mechanism design without money. In: Proceedings of the 10th ACM conference on electronic commerce, pp 177–186. https://doi.org/10.1145/1566374.1566401
Schummer J, Vohra R (2002) Strategy-proof location on a network. J Econ Theory 104(2):405–428. https://doi.org/10.1006/jeth.2001.2807
Sui X, Boutilier C (2015) Approximately strategy-proof mechanisms for (constrained) facility location. In: Proceedings of the 14th international conference on autonomous agents and multiagent systems, pp 605–613
Serafino P, Ventre C (2016) Heterogeneous facility location without money. Theoret Comput Sci 636:27–46. https://doi.org/10.1016/j.tcs.2016.04.033
Tang Z, Wang C, Zhang M, Zhao Y (2022) Strategyproof facility location with limited locations. J Oper Res Soc China. https://doi.org/10.1007/s40305-021-00378-1
Xu X, Li B, Li M, Duan L (2021) Two-facility location games with minimum distance requirement. J Artific Intell Res 70:719–756. https://doi.org/10.1613/jair.1.12319
Ye D, Mei L, Zhang Y (2015) Strategy-proof mechanism for obnoxious facility location on a line. In: International computing and combinatorics conference, pp 45–56. https://doi.org/10.1007/978-3-319-21398-9_4
Yuan H, Wang K, Fong KC, Zhang Y, Li M (2016) Facility location games with optional preference. In: Proceedings of the 22nd European conference on artificial intelligence, pp 1520–1527. https://doi.org/10.3233/978-1-61499-672-9-1520
Zhang Q, Li M (2014) Strategyproof mechanism design for facility location games with weighted agents on a line. J Comb Optim 28(4):756–773. https://doi.org/10.1007/s10878-013-9598-8
Zhao Q, Liu W, Fang Q, Nong Q (2023) Constrained heterogeneous two-facility location games with max-variant cost. J Comb Optim 45(3):90. https://doi.org/10.1007/s10878-023-01017-6
Zou S, Li M (2015) Facility location games with dual preference. In: Proceedings of the 14th international conference on autonomous agents and multiagent systems, pp 615–623
Funding
This research was supported in part by the National Natural Science Foundation of China (12201590, 12171444, 11971447, 11871442).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
None.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Zhao, Q., Liu, W., Nong, Q. et al. Constrained heterogeneous two-facility location games with sum-variant. J Comb Optim 47, 65 (2024). https://doi.org/10.1007/s10878-024-01163-5
Accepted:
Published:
DOI: https://doi.org/10.1007/s10878-024-01163-5