In the k-level facility location problem with penalties,each client will be either serviced or rejected completely. And if the client is planned to be serviced, then it must be connected to asequence of k different kinds of facilities located in k levels of hierarchy. The total cost including the facility cost, connection cost and penalty cost will be jointly paid by all the clients. In the corresponding game of the k-level facility location problem with penalties, called the k-level facility location game with penalties, the total cost should be allocated to different clients. This work set out a cost-sharing scheme for the k-level facility location game with penalties that is cross-monotonic, competitive, and the approximate cost recovery is 6.
Feng-Min Wang, Jia-Jia Wang, Na Li, Yan-Jun Jiang, Shi-Cheng Li
. A Cost-Sharing Scheme for the k-Level Facility Location Game with Penalties[J]. Journal of the Operations Research Society of China, 2022
, 10(1)
: 173
-182
.
DOI: 10.1007/s40305-021-00345-w
[1] Asadi, M., Niknafs, A., Ghodsi, M.:An approximation algorithm for the k-level uncapacitated facility location problem with penalties. In:Advances in Computer Science and Engineering, pp. 41-49(2009)
[2] Pál, M., Tardös, E:Group strategyproof mechanisms via primal-dual algorithms. In:Proceedings of FOCS, pp. 584-593(2003)
[3] Wang, Z., Xu, D.:A cost-sharing method for an uncapacitated facility location game with penalties. J. Syst. Sci. Complexity 25(2), 287-292(2012)
[4] Xu, D., Du, D.:The k-level facility location game. Oper. Res. Lett. 34(4), 421-426(2006)
[5] Immorlica, N., Mahdian, M., Mirrokni, V.S.:Lower bounds for cost sharing and group-strategyproof mechanisms. ACM-SIAM Symposium on Discrete Algorithms (2004)
[6] Charikar, M., Khuller, S., Mount, D., Narasimhan, G.:Algorithms for facility location problems with outliers. In:Proceedings of Symposium on Discrete Algorithms, pp. 642-651(2001)
[7] Sahin, G., Sural, H.:A review of hierarchical facility location models. Comput. Oper. Res. 34(8), 2310-2331(2007)
[8] Fotakis, D., Tzamos, C.:On the Power of deterministic mechanisms for facility location games. ACM Trans. Econ. Comput. 2(4), 1-37(2013)
[9] Chen, X., Hu, X., Jia, X., Li, M., Tang, Z., Wang, C.:Mechanism design for two-opposite-facility location games with penalties on distance. In:International Symposium on Algorithmic Game Theory, pp. 256-260(2018)
[10] Li, Y., Xu, D.:Soft-capacity facility location game. Acta Mathematicae Applicatae Sinica 26(1), 93-98(2010)
[11] Moulin, H., Shenker, S.:Strategyproof sharing of submodular costs:budget balance versus efficiency. Econ. Theor. 18, 511-533(2001)
[12] Li, G., Xu, D., Du, D., Wu, C.:Approximation algorithms for the multilevel facility location problem with linear/submodular penalties. In:International Workshop on Frontiers in Algorithmics, pp. 162-169(2015)
[13] Ding, Y., Liu, W., Chen, X., Fang, Q., Nong, Q.:Facility location game with envy ratio. Comput. Ind. Eng. https://doi.org/10.1016/j.cie.2020.106710(2020)
[14] Mei, L., Li, M., Ye, D., Zhang, G.:Strategy-proof mechanism design for facility location games:revisited. In:Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pp. 1463-1464(2016)
[15] Ageev, A., Ye, Y., Zhang, J.:Improved combinatorial approximation algorithms for the k-level facility location problem. SIAM J. Discret. Math. 18, 207-217(2003)
[16] Li,M.,Wang,C.,Zhang,M.:Budgetedfacilitylocationgameswithstrategicfacilities.In:Proceedings of the 29th International Joint Conference on Artificial Intelligence, pp. 400-406(2020)
[17] Jain, K., Vazirani, V.V.:Primal-dual approximation algorithms for metric facility location and kmedian probelms. J. ACM 48, 274-296(2001)
[18] Mettu, R.R., Plaxton, C.G.:The online median problem. SIAM J. Comput. 32(3), 816-832(2003)
[19] Bumb, A.F., Kern, W.:A simple dual ascent algorithm for the multilevel facility location problem. In:Proceedings of APPROX, pp. 55-62(2001)
[20] Li, G., Li, Y., Shu, J., Xu, D.:A cross-monotonic cost sharing scheme for the concave facility location game. J. Glob. Optim. 56(4), 1325-1334(2013)
