Abstract
This study explores heterogeneous two-facility location mixed mechanisms, aiming to develop an approach for positioning two facilities that ensures agent strategyproofness while minimizing social costs. We introduce a mixed mechanism that achieves an approximation ratio of \( \frac{25}{8} \), demonstrating a significant improvement over the latest deterministic mechanism, which has an approximation ratio of \( \frac{17}{4} \).
This work is supported by National Science Foundation of China (No. 12371099) and Natural Science Foundation of Shandong Province of China (No. ZR2024MA015).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Anastasiadis, E., Deligkas, A.: Heterogeneous facility location games. arXiv preprint arXiv:2005.03095 (2020)
Anshelevich, E., Filos-Ratsikas, A., Voudouris, A.A.: The distortion of distributed metric social choice. Artif. Intell. 308, 103713 (2022)
Babaioff, M., Feldman, M., Tennenholtz, M.: Mechanism design with strategic mediators. ACM Trans. Econ. Comput. (TEAC) 4(2), 1–48 (2016)
Cai, Q., Filos-Ratsikas, A., Tang, P.: Facility location with minimax envy. In: AAAI Press/International Joint Conferences on Artificial Intelligence (2016)
Cheng, Y., Yu, W., Zhang, G.: Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theor. Comput. Sci. 497, 154–163 (2013)
Duan, L., Li, B., Li, M., Xu, X.: Heterogeneous two-facility location games with minimum distance requirement. In: AAMAS, pp. 1461–1469 (2019)
Feigenbaum, I., Sethuraman, J.: Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location models. In: Workshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015)
Feigenbaum, I., Sethuraman, J., Ye, C.: Approximately optimal mechanisms for strategyproof facility location: minimizing LP norm of costs. Math. Oper. Res. 42(2), 434–447 (2017)
Feldman, M., Wilf, Y.: Strategyproof facility location and the least squares objective. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pp. 873–890 (2013)
Filos-Ratsikas, A., Kanellopoulos, P., Voudouris, A.A., Zhang, R.: Settling the distortion of distributed facility location. arXiv preprint arXiv:2301.01604 (2023)
Filos-Ratsikas, A., Li, M., Zhang, J., Zhang, Q.: Facility location with double-peaked preferences. Auton. Agent. Multi-Agent Syst. 31(6), 1209–1235 (2017). https://doi.org/10.1007/s10458-017-9361-0
Fong, C.K.K., Li, M., Lu, P., Todo, T., Yokoo, M.: Facility location games with fractional preferences. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32 (2018)
Fotakis, D., Tzamos, C.: Winner-imposing strategyproof mechanisms for multiple facility location games. Theor. Comput. Sci. 472, 90–103 (2013)
Hossain, S., Micha, E., Shah, N.: The surprising power of hiding information in facility location. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 2168–2175 (2020)
Kanellopoulos, P., Voudouris, A.A., Zhang, R.: On discrete truthful heterogeneous two-facility location. SIAM J. Discret. Math. 37(2), 779–799 (2023)
Kyropoulou, M., Ventre, C., Zhang, X.: Mechanism design for constrained heterogeneous facility location. In: Fotakis, D., Markakis, E. (eds.) SAGT 2019. LNCS, vol. 11801, pp. 63–76. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30473-7_5
Li, M., Lu, P., Yao, Y., Zhang, J.: Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio. arXiv preprint arXiv:1907.08918 (2019)
Menon, V., Larson, K.: Mechanism design for locating a facility under partial information. In: Fotakis, D., Markakis, E. (eds.) SAGT 2019. LNCS, vol. 11801, pp. 49–62. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30473-7_4
Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. ACM Trans. Econ. Comput. (TEAC) 1(4), 1–26 (2013)
Serafino, P., Ventre, C.: Truthful mechanisms without money for non-utilitarian heterogeneous facility location. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 29 (2015)
Serafino, P., Ventre, C.: Heterogeneous facility location without money. Theor. Comput. Sci. 636, 27–46 (2016)
Yan, X., Chen, Y.: Strategyproof facility location mechanisms with richer action spaces. arXiv preprint arXiv:2002.07889 (2020)
Zhao, Q., Liu, W., Fang, Q., Nong, Q.: Constrained heterogeneous two-facility location games with max-variant cost. In: International Workshop on Frontiers in Algorithmics, pp. 25–43. Springer (2022)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Xu, M., Liu, Q., Li, M., Zhou, Y. (2025). Randomized Mechanisms for Improved Approximation Ratios in Heterogeneous Two-Facility Location. In: Du, D., Han, L., Xu, D. (eds) Combinatorial Optimization and Applications. COCOA 2024. Lecture Notes in Computer Science, vol 15434. Springer, Singapore. https://doi.org/10.1007/978-981-96-4445-2_7
Download citation
DOI: https://doi.org/10.1007/978-981-96-4445-2_7
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-96-4444-5
Online ISBN: 978-981-96-4445-2
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
