Facility Reallocation on the Line
Tóm tắt
We consider a multi-stage facility reallocation problems on the real line, where a facility is being moved between time stages based on the locations reported by n agents. The aim of the reallocation algorithm is to minimise the social cost, i.e., the sum over the total distance between the facility and all agents at all stages, plus the cost incurred for moving the facility. We study this problem both in the offline setting and online setting. In the offline case the algorithm has full knowledge of the agent locations in all future stages, and in the online setting the algorithm does not know these future locations and must decide the location of the facility on a stage-per-stage basis. We derive the optimal algorithm in both cases. For the online setting we show that its competitive ratio is
$$(n+2)/(n+1)$$
. As neither of these algorithms turns out to yield a strategy-proof mechanism, we propose another strategy-proof mechanism which has a competitive ratio of
$$(n+3)/(n+1)$$
for odd n and
$$(n+4)/n$$
for even n, which we conjecture to be the best possible. We also consider a generalisation with multiple facilities and weighted agents, for which we show that the optimum can be computed in polynomial time for a fixed number of facilities.
Tài liệu tham khảo
Ahmadian, S., Friggstad, S., Swamy, C.: Local-search based approximation algorithms for mobile facility location problems. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1607–1621. Society for Industrial and Applied Mathematics, (2013)
An, H.-C., Norouzi-Fard, A., Svensson, O.: Dynamic facility location via exponential clocks. ACM Trans. Algo. 13(2), 21:1-21:20 (2017)
Chen, Z., Fong, K.C.K., Li, M., Wang, K., Yuan, H., Yong, Z.: Facility location games with optional preference. Theoret. Comput. Sci. 847, 185–197 (2020)
Divéki, G., Imreh, C.: Online facility location with facility movements. CEJOR 19(2), 191–200 (2011)
Downs, A.: An economic theory of political action in a democracy. J. Polit. Econ. 65(2), 135–150 (1957)
Duan, L., Li, B., Li, M., Xu, X.: Heterogeneous two-facility location games with minimum distance requirement. In Proceedings of the 18th International Conference on Autonomous Agents and Multi-Agent Systems, pages 1461—1469. International Foundation for Autonomous Agents and Multiagent Systems, (2019)
Eisenstat, D., Mathieu, C., Schabanel, N.: Facility location in evolving metrics. In Proceedings of the International Colloquium on Automata, Languages and Programming, pages 459–470. Springer, (2014)
Feldman, M., Fiat, A., Golomb, I.: On voting and facility location. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 269–286. ACM, (2016)
Filos-Ratsikas, Aris, Li, Minming, Zhang, Jie, Zhang, Qiang: Facility location with double-peaked preferences. Auton. Agent. Multi-Agent Syst. 31(6), 1209–1235 (2017)
Fotakis, D.: Online and incremental algorithms for facility location. ACM SIGACT News 42(1), 97–131 (2011)
Fotakis, D., Kavouras, L., Kostopanagiotis, P., Lazos, P., Skoulakis, S., Zarifis, N.: Reallocating multiple facilities on the line. Theoret. Comput. Sci. 858, 13–34 (2021)
Fotakis, D., Tzamos, C.: On the power of deterministic mechanisms for facility location games. ACM Trans. Econ. Comput. 2(4), 15 (2014)
Friggstad, Z., Salavatipour, M.R.: Minimizing movement in mobile facility location problems. ACM Trans. Algo. 7(3), 28 (2011)
Gupta, A., Talwar, K., Wider, U.: Changing bases: Multistage optimization for matroids and matchings. In Proceedings of the International Colloquium on Automata, Languages and Programming, pages 563–575. Springer, (2014)
de Keijzer, B., Wojtczak, D.: Facility reallocation on the line. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 188–194. AAAI Press, (2018)
Lin, H., Bilmes, J.: Learning mixtures of submodular shells with application to document summarization. In Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence (UAI’12), pages 479–490. AUAI Press, (2012)
Lu, P., Sun, X., Wang, Y., Zhu, Z. A.: Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM Conference on Electronic Commerce, pages 315–324. ACM, (2010)
Lu, P., Wang, Y., Zhou, Y.: Tighter bounds for facility games. In Proceedings of the International Workshop on Internet and Network Economics, pages 137–148. Springer, (2009)
Megiddo, N., Supowit, K.J.: On the complexity of some common geometric location problems. SIAM J. Comput. 13(1), 182–196 (1984)
Megiddo, N., Zemel, E., Hakimi, S.L.: The maximum coverage location problem. SIAM J. Alg. Disc. Meth. 4(2), 253–261 (1983)
Miyagawa, E.: Locating libraries on a street. Soc. Choice Welfare 18(3), 527–541 (2001)
Moulin, H.: On strategy-proofness and single peakedness. Pub. Choice 35(4), 437–455 (1980)
Procaccia, A. D., Tennenholtz, M.: Approximate mechanism design without money. In Proceedings of the 10th ACM Conference on Electronic Commerce, pages 177–186. ACM, (2009)
Procaccia, A. D., Wajc, D., Zhang, H.: Approximation-variance tradeoffs in facility location games. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence. AAAI Press, (2017)
Serafino, P., Ventre, C.: Truthful mechanisms without money for non-utilitarian heterogeneous facility location. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pages 1029–1035. AAAI Press, (2015)
Song, H. O., Jegelka, S., Vivek, R., Kevin, M.: Deep metric learning via facility location. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2206–2214. IEEE, (2017)
Sui, X., Boutilier, C., Sandholm, T.: Analysis and optimization of multi-dimensional percentile mechanisms. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pages 367–374. AAAI Press, (2013)
Todo, T., Iwasaki, A., Yokoo, M.: False-name-proof mechanism design without money. In The 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 2, pages 651–658. International Foundation for Autonomous Agents and Multiagent Systems, (2011)
Tschiatschek, S., Iyer, R. K., Wei, H., Bilmes, J. A.: Learning mixtures of submodular functions for image collection summarization. In Advances in Neural Information Processing Systems, pages 1413–1421. MIT Press, (2014)
Weber, A.: Über den standort der industrien, 1. teil: Reine theorie des standortes. (on the location of industries), (1909)
Xu, X., Li, B., Li, M., Duan, L.: Two-facility location games with minimum distance requirement. J. Arti. Intell. Res. 70, 719–756 (2021)
Zou,S., Li, M.: Facility location games with dual preference. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 615–623. International Foundation for Autonomous Agents and Multiagent Systems, (2015)