Abstract
We consider k-Facility Location games, where n strategic agents report their locations on the real line and a mechanism maps them to k facilities. Each agent seeks to minimize his connection cost, given by a nonnegative increasing function of his distance to the nearest facility. Departing from previous work, that mostly considers the identity cost function, we are interested in mechanisms without payments that are (group) strategyproof for any given cost function, and achieve a good approximation ratio for the social cost and/or the maximum cost of the agents. We present a randomized mechanism, called Equal Cost, which is group strategyproof and achieves a bounded approximation ratio for all k and n, for any given concave cost function. The approximation ratio is at most 2 for Max Cost and at most n for Social Cost. To the best of our knowledge, this is the first mechanism with a bounded approximation ratio for instances with \(k \ge 3\) facilities and any number of agents. Our result implies an interesting separation between deterministic mechanisms, whose approximation ratio for Max Cost jumps from 2 to unbounded when k increases from 2 to 3, and randomized mechanisms, whose approximation ratio remains at most 2 for all k. On the negative side, we exclude the possibility of a mechanism with the properties of Equal Cost for strictly convex cost functions. We also present a randomized mechanism, called Pick the Loser, which applies to instances with k facilities and only \(n = k+1\) agents. For any given concave cost function, Pick the Loser is strongly group strategyproof and achieves an approximation ratio of 2 for Social Cost.
Similar content being viewed by others
Notes
The approximation ratio of a mechanism for k-Facility Location is bounded if it is a function of n and k. We highlight that this property is essentially objective-independent, since any mechanism with a bounded approximation ratio for e.g., Max Cost also has a bounded approximation for Social Cost and for the objective of minimizing the \(L_p\) norm of the agents’ costs, for any \(p \ge 1\), and vice versa.
References
Alon, N., Feldman, M., Procaccia, A.D., Tennenholtz, M.: Strategyproof approximation of the minimax on networks. Math. Oper. Res. 35(3), 513–526 (2010)
Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA ’07)
Barberà, S.: An introduction to strategyproof social choice functions. Soc. Choice Welf. 18, 619–653 (2001)
Dokow, E., Feldman, M., Meir, R., Nehama, I.: Mechanism design on discrete lines and cycles. In: Proceedings of the 13th ACM Conference on Electronic Commerce (EC ’12), pp. 423–440 (2012)
Escoffier, B., Gourvès, L., Thang, N.K., Pascual, F., Spanjaard, O.: Strategy-proof mechanisms for facility location games with many facilities. In: Proceedings of the 2nd International Conference on Algorithmic Decision Theory (ADT ’11), LNAI 6992, pp. 67–81 (2011)
Feldman, M., Wilf, Y.: Strategyproof facility location and the least squares objective. In: Proceedings of the 14th ACM Conference on Electronic Commerce (EC ’13)
Fotakis, D., Tzamos, C.: On the power of deterministic mechanisms for facility location games. ACM Trans. Econ. Comput. 2(4), 15 (2014). (1–37)
Fotakis, D., Tzamos, C.: Winner-imposing strategyproof mechanisms for multiple Facility Location games. Theor. Comput. Sci. 472, 90–103 (2013)
Koutsoupias, E.: Scheduling without payments. In: Proceedings of the 4th International Symposium on Algorithmic Game Theory (SAGT ’11), Volume 6982 of LNCS, pp. 143–153 (2011)
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 (EC ’10)
Lu, P., Wang, Y., Zhou, Y.: Tighter bounds for facility games. In: Proceedings of the 5th Workshop on Internet and Network Economics (WINE ’09), LNCS 5929, pp. 137–148 (2009)
Mirchandani, P.B., Francis, R.L.: Discrete Location Theory. Wiley, New York (1980)
Miyagawa, E.: Locating libraries on a street. Soc. Choice Welf. 18, 527–541 (2001)
Moulin, H.: On strategy-proofness and single-peakedness. Public Choice 35, 437–455 (1980)
Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
Nissim, K., Smorodinsky, R., Tennenholtz, M.: Approximately optimal mechanism design via Differential Privacy. In: Proceedings of the 3rd Conference on Innovations in Theoretical Computer Science (ITCS ’12)
Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. In: Proceedings of the 10th ACM Conference on Electronic Commerce (EC ’09), pp. 177–186 (2009)
Schummer, J., Vohra, R.V.: Strategyproof location on a network. J. Econ. Theory 104, 405–428 (2002)
Sprumont, Y.: Strategyproof collective choice in economic and political environments. Can. J. Econ. 28(1), 68–108 (1995)
Sui, X., Boutilier, C., Sandholm, T.: Analysis and optimization of multi-dimensional percentile mechanisms. In: Proceedings of the 4th International Workshop on Computational Social Choice (COMSOC ’12) (2012)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by the project AlgoNow, co-financed by the European Union (European Social Fund—ESF) and Greek national funds, through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF)—Research Funding Program: THALES, investing in knowledge society through the European Social Fund. A preliminary version of this work appeared in the Proceedings of the 14th ACM Conference on Electronic Commerce (EC 2013), M. Kearns, R. P. McAfee, and É. Tardos (Editors), pp. 435–452, ACM, 2013.
Rights and permissions
About this article
Cite this article
Fotakis, D., Tzamos, C. Strategyproof Facility Location for Concave Cost Functions. Algorithmica 76, 143–167 (2016). https://doi.org/10.1007/s00453-015-0026-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-015-0026-6