Abstract
In classic obnoxious facility games [5, 6, 12], each agent i has a private location \(x_i\) on a closed interval [0, 1] and one facility y is planned to build on the interval according to the bids of all the agents. In this paper we consider obnoxious effects among the game by introducing two thresholds \(d_1\) and \(d_2\) into utility functions, where \(0 \le d_1 \le d_2 \le 1\). Let \(d(y, x_i) = |y - x_i|\) be the distance between agent i and facility y. The utility function of agent i is 0 if \(d(y, x_i)\) is at most \(d_1\); 1 if \(d(y, x_i)\) is at least \(d_2\); otherwise a linear increasing function between 0 and 1. Each agent aims to get a largest possible utility while the social welfare is to maximize the sum of all the agents’ utilities.
The classic obnoxious facility game is a special case of our problem when \(d_1 =0\) and \(d_2=1\). We show that if \(d_1 = d_2\), a mechanism that outputs the leftmost optimal facility location is strategy-proof. If \(d_1 \ge \frac{1}{2}\), we show the problem cannot have any bounded deterministic strategy-proof mechanism. By further detailed analysis, if the thresholds \(d_1\), \(d_2\) are restricted to some ranges, we design strategy-proof mechanisms and provide the approximation ratios with respect to \(d_1\) and \(d_2\).
Research was partially supported by the Nature Science Foundation of Zhejiang Province (NO. LQ15A010001).
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
Alon, N., Feldman, M., Procaccia, A.D., Tennenholtz, M.: Strategy proof approximation of the minimax on networks. Math. Oper. Res. (MOR) 35(3), 513–526 (2010)
Alon, N., Feldman, M., Procaccia, A.D., Tennenholtz, M.: Strategyproof approximation for location on networks (2009). arXiv.org/abs/0907.2049
Brimberg, J., Juel, H.: A bi-criteria model for locating a semi-desirable facility in the plane. Eur. J. Oper. Res. (EJOR) 106(1), 144–151 (1998)
Cheng, Y., Han, Q., Zhang, G.: Obnoxious facility game with a bounded service range. In: Chan, T.-H.H., Lau, L.C., Trevisan, L. (eds.) TAMC 2013. LNCS, vol. 7876, pp. 272–281. Springer, Heidelberg (2013)
Cheng, Y., Yu, W., Zhang, G.: Mechanisms for obnoxious facility game on a path. In: Wang, W., Zhu, X., Du, D.-Z. (eds.) COCOA 2011. LNCS, vol. 6831, pp. 262–271. Springer, Heidelberg (2011)
Cheng, Y., Yu, W., Zhang, G.: Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theor. Comput. Sci. (TCS) 35(3), 513–526 (2011)
Escoffier, B., Gourvès, L., Kim Thang, N., Pascual, F., Spanjaard, O.: Strategy-proof mechanisms for facility location games with many facilities. In: Brafman, R. (ed.) ADT 2011. LNCS, vol. 6992, pp. 67–81. Springer, Heidelberg (2011)
Feigenbaum, I., Sethuraman, J.: Strategy proof mechanisms for one-dimensional hybrid and obnoxious facility location models. In: Workshops at the 29th AAAI Conference on Artificial Intelligence (2015)
Feldman, M., Wilf, Y.: Strategyproof facility location and the least squares objective. In: The 14th ACM Conference on Electronic Commerce (EC), pp. 873–890 (2013)
Filos-Ratsikas, A., Li, M., Zhang, J., Zhang, Q.: Facility location with double-peaked preferences. In: The 29th Conference on Artificial Intelligence (AAAI) (2015)
Fotakis, D., Tzamos, C.: Strategy proof facility location for concavecost functions. In: The 14th ACM Conference on Electronic Commerce (EC), pp. 435–452 (2013)
Ibara, K., Nagamochi, H.: Characterizing mechanisms in obnoxious facility game. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 301–311. Springer, Heidelberg (2012)
Lu, P., Sun, X., Wang, Y., Zhu, Z.A.: Asymptotically optimal strategy-proof mechanisms for two-facility games. In: The 11th ACM Conference on Electronic Commerce (EC), pp. 315–324 (2010)
Lu, P., Wang, Y., Zhou, Y.: Tighter bounds for facility games. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 137–148. Springer, Heidelberg (2009)
Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. In: The 10th ACM conference on Electronic Commerce (EC), pp. 177–186 (2009)
Yapicioglu, H., Smith, A.E., Dozier, G.: Solving the semi-desirable facility location problem using bi-objective particle swarm. Eur. J. Oper. Res. (EJOR) 177(2), 733–749 (2007)
Ye, D., Mei, L., Zhang, Y.: Strategy-proof mechanism for obnoxious facility location on a line. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 45–56. Springer, Heidelberg (2015)
Zhang, Q., Li, M.: Strategy proof mechanism design for facility location games with weighted agents on a line. J. Comb. Optim. (JOCO) 28(4), 756–773 (2014)
Zou, S., Li, M.: Facility location games with dual preference. In: The International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 615–623 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Mei, L., Ye, D., Zhang, G. (2016). Mechanism Design for One-Facility Location Game with Obnoxious Effects. In: Zhu, D., Bereg, S. (eds) Frontiers in Algorithmics. FAW 2016. Lecture Notes in Computer Science(), vol 9711. Springer, Cham. https://doi.org/10.1007/978-3-319-39817-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-39817-4_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-39816-7
Online ISBN: 978-3-319-39817-4
eBook Packages: Computer ScienceComputer Science (R0)