Abstract
In a facility game one or more facilities are placed in a metric space to serve a set of selfish agents whose addresses are their private information. In a classical facility game, each agent wants to be as close to a facility as possible, and the cost of an agent can be defined as the distance between her location and the closest facility. In an obnoxious facility game, each agent wants to be far away from all facilities, and her utility is the distance from her location to the facility set. The objective of each agent is to minimize her cost or maximize her utility. An agent may lie if, by doing so, more benefit can be obtained. We are interested in social choice mechanisms that do not utilize payments. The game designer aims at a mechanism that is strategy-proof, in the sense that any agent cannot benefit by misreporting her address, or, even better, group strategy-proof, in the sense that any coalition of agents cannot all benefit by lying. Meanwhile, it is desirable to have the mechanism to be approximately optimal with respect to a chosen objective function. Several models for such approximation mechanism design without money for facility games have been proposed. In this paper we briefly review these models and related results for both deterministic and randomized mechanisms, and meanwhile we present a general framework for approximation mechanism design without money for facility games.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Nisan, N., Ronen, A.: Algorithmic mechanism design. Game Econ. Behav. 35(1–2), 166–196 (2001)
Nisan, N.: Introduction to mechanism design (for computer scientists). In: Nisan, N., Roughgarden, T., Tardos, E.,Vazirani, V. (eds.) Algorithmic Game Theory, Chap. 9. Cambridge University Press, Cambridge (2007)
Rothkopf, M.: Thirteen reasons the Vickrey-Clarke-Groves process is not practical. Oper. Res. 55(2), 191–197 (2007)
Schummer, J., Vohra, R.V.: Mechanism design without money. In: Nisan, N., Roughgarden, T., Tardos, E.,Vazirani, V. (eds.) Algorithmic Game Theory, Chap. 10. Cambridge University Press, Cambridge (2007)
Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. In: 10th ACM Conference on Electronic Commerce, pp. 177–186. ACM, New York (2009)
Drezner, Z., Hamacher, H.: Facility Location: Applications and Theory. Springer, Berlin (2002)
Kariv, O., Hakimi, S.L.: An algorithmic approach to network location poblems. I. The p-centers. SIAM J. Appl. Math. 37, 441–461 (1979)
Kariv, O., Hakimi, S.L.: An algorithmic approach to network location poblems. II. The p-medians. SIAM J. Appl. Math. 37, 539–560 (1979)
Cappanera, P.: A survey on obnoxious facility location problems. Technical Report: TR-99-11 (1999). Available via DIALOG. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.2783
Tamir, A.: Obnoxious facility location on graphs. SIAM J. Discrete Math. 4, 550–567 (1991)
Zelinka, B.: Medians and peripherian of trees. Arch. Math. 4, 87–95 (1968)
Moulin, H.: On strategy-proofness and single-peakedness. Public Choice 35, 437–455 (1980)
Alon, N., Feldman, M., Proccia, A.D., Tennenholtz, M.: Strategyproof approximation mechanisms for location on networks. Computing Research Repository-CORR, abs/0907.2049 (2009)
Schummer, J., Vohra, R.V.: Strategy-proof location on a network. J. Econ. Theory 104(2), 405–428 (2004)
Dekel, O., Fischer, F., Procaccia, A.D.: Incentive compatible regression learning. J. Comput. Syst. Sci. 76(8), 759–777 (2010)
Lu, P., Wang, Y., Zhou, Y.: Tighter boundes for facility games. In: Leonardi, S. (ed.) WINE 2009. Lecture Notes in Computer Science, vol. 5929, pp. 137–148. Springer, Heidelberg (2009)
Lu, P., Sun, X., Wang, Y., Zhu, Z.: Asymptotically optimal strategy-proof mechanisms for two-facility games. In: 11th ACM Conference on Electronic Commerce, pp. 315–324. ACM, New York (2010)
Gupta, A., Ligett, K., McSherry, F., Roth, A., Talwar, K.: Differentially private combinatorial optimization. In: SODA 2010: Proceedings of the Twenty-First ACM-SIAM Symposium on Discrete Algorithms, pp. 1106–1125 (2010)
McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: FOCS 2007: Proceedings of the Forty-Eighth IEEE Symposium on Foundations of Computer Science, pp. 94–103 (2007)
Nissim, K., Smorodinsky, R., Tennenholtz, M.: Approximately optimal mehcanism design via differential privacy. Computing Research Repository-CORR, abs/1004.2888 (2010)
Fotakis, D., Tzamos, C.: Winner-imposing strategy-proof mechanisms for multiple facility location games. In: Saberi, A. (ed.) WINE 2010. Lecture Notes in Computer Science, vol. 6484, pp. 234–245. Springer, Heidelberg (2010)
Meyerson, A.: Online facility location. In: FOCS 2001: Proceedings of the Forty-Second IEEE Symposium on Foundations of Computer Science, pp. 426–431 (2001)
Escoffier, B., Gourves, L., Thang, N., Pascual, F., Spanjaard, O.: Strategy-proog mechanisms for facility location games with many facilities. In: Brafman, R.I., Roberts, F.S., Tsoukià s, A. (eds.) ADT 2011. Lecture Notes in Computer Science, vol. 6992, pp. 67–81. Springer, Heidelberg (2011)
Barberà , S., Berga, D., Moreno, B.: Single-dipped preferences. Working paper (2009)
Han, Q., Du, D.: Moneyless strategy-proof mechanism on single-dipped policy domain: characerization and applications. Working paper (2012)
Ibara, K., Nagamochi, H.: Charactering mechanisms in obnoxious facility game. In: Lin, G. (ed.) COCOA 2012. Lecture Notes in Computer Science, vol. 7402, pp. 301–311. Springer, Heidelberg (2012)
Manjunath, V.: Efficient and Strategy-Proof Social Choice When Preferences are Singledipped. Mimeo (2009)
Peremans, W., Storcken, T.: Strategy-proofness on single-dipped preferences domains. In: Proceedings of the International Conference, Logic, Game Theory, and Social Choice, pp. 296–313 (1999)
Cheng, Y., Yu, W., Zhang, G.: Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theor. Comput. Sci. 497, 154–163 (2013)
Church, R., Garfinkel, R.: Locating an obnoxious facility on a network. Transp. Sci. 12, 107–118 (1978)
Ting, S.: A linear-time algorithm for maxisum facility location on tree networks. Trans. Sci. 18, 76–84 (1984)
Cheng, Y., Han, Q., Yu,W., Zhang, G.: Obnoxious facility game with a bounded service range. In: Chan, T.-H.H., Lau, L., Trevisan, L. (eds.) TAMC 2013. Lecture Notes in Computer Science, vol. 7876, pp. 272–281. Springer, Heidelberg (2013)
Acknowledgements
Research was partially supported by the Nature Science Foundation of China (No. 11301475) and the Nature Science Foundation of Zhejiang Province, China (No. LQ12A01011).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Cheng, Y., Zhou, S. (2015). A Survey on Approximation Mechanism Design Without Money for Facility Games. In: Gao, D., Ruan, N., Xing, W. (eds) Advances in Global Optimization. Springer Proceedings in Mathematics & Statistics, vol 95. Springer, Cham. https://doi.org/10.1007/978-3-319-08377-3_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-08377-3_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08376-6
Online ISBN: 978-3-319-08377-3
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)