Weitere Artikel dieser Ausgabe durch Wischen aufrufen
Aris Filos-Ratsikas and Jie Zhang were supported by the ERC Advanced Grant 321171 (ALGAME) and the Sino-Danish Center for the Theory of Interactive Computation, funded by the Danish National Research Foundation and the National Science Foundation of China (under the Grant 61061130540), and by the Center for research in the Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. Minming Li was partly supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 117913]. Qiang Zhang was supported by FET IP Project MULTIPEX 317532.
We study the problem of locating a single facility on a real line based on the reports of self-interested agents, when agents have double-peaked preferences, with the peaks being on opposite sides of their locations. We observe that double-peaked preferences capture real-life scenarios and thus complement the well-studied notion of single-peaked preferences. As a motivating example, assume that the government plans to build a primary school along a street; an agent with single-peaked preferences would prefer having the school built exactly next to her house. However, while that would make it very easy for her children to go to school, it would also introduce several problems, such as noise or parking congestion in the morning. A 5-min walking distance would be sufficiently far for such problems to no longer be much of a factor and at the same time sufficiently close for the school to be easily accessible by the children on foot. There are two positions (symmetrically) in each direction and those would be the agent’s two peaks of her double-peaked preference. Motivated by natural scenarios like the one described above, we mainly focus on the case where peaks are equidistant from the agents’ locations and discuss how our results extend to more general settings. We show that most of the results for single-peaked preferences do not directly apply to this setting, which makes the problem more challenging. As our main contribution, we present a simple truthful-in-expectation mechanism that achieves an approximation ratio of \(1+b/c\) for both the social and the maximum cost, where b is the distance of the agent from the peak and c is the minimum cost of an agent. For the latter case, we provide a 3 / 2 lower bound on the approximation ratio of any truthful-in-expectation mechanism. We also study deterministic mechanisms under some natural conditions, proving lower bounds and approximation guarantees. We prove that among a large class of reasonable strategyproof mechanisms, there is no deterministic mechanism that outperforms our truthful-in-expectation mechanism. In order to obtain this result, we first characterize mechanisms for two agents that satisfy two simple properties; we use the same characterization to prove that no mechanism in this class can be group-strategyproof.
Ashlagi, I., Fischer, F., Kash, I., & Procaccia, A. D. (2010). Mix and match. In Proceedings of the 11th ACM conference on Electronic commerce (ACM-EC) (pp. 305–314). ACM.
Black, D. (1957). The theory of committees and elections. Dordrecht: Kluwer Academic Publishers. (reprint at 1986). MATH
Cai, Q., Filos-Ratsikas, A., Filos, A., & Tang, P. (2016). Facility location with minimax envy. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI) (pp. 137–143).
Caragiannis, I., Filos-Ratsikas, A., & Procaccia, A. D. (2011). An improved 2-agent kidney exchange mechanism. In Proceedings of the 7th Workshop of Internet and Network Economics (WINE) (pp. 37–48). Springer.
Cheng, Y., Yu, W., & Zhang, G. (2011). Mechanisms for obnoxious facility game on a path. In International Conference on Combinatorial Optimization and Applications (pp. 262–271). Springer.
Conitzer, V. (2007). Eliciting single-peaked preferences using comparison queries. In Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems (p. 65). ACM.
Cooter, R. D. (2002). The strategic constitution. Princeton: Princeton University Press.
Dokow, E., Feldman, M., Meir, R., & Nehama, I. (2012). Mechanism design on discrete lines and cycles. In Proceedings of the 13th ACM Conference on Electronic Commerce (ACM-EC) (pp. 423–440).
Dughmi, S., & Gosh, A. (2010). Truthful assignment without money. In Proceedings of the 11th ACM conference on Electronic commerce (ACM-EC) (pp. 325–334).
Egan, P. J. (2013). “Do something” politics and double-peaked policy preferences. Journal of Politics, 76(2), 333–349. CrossRef
Escoffier, B., Gourvès, L., Thang, N. K., Pascual, F., & Spanjaard, O. (2011). Strategy-proof mechanisms for facility location games with many facilities. In The 2nd International Conference on Algorithmic Decision Theory, (pp. 67–81). Berlin, Heidelberg: Springer.
Escoffier, B., Lang, J., & Öztürk, M. (2008). Single-peaked consistency and its complexity. In The 18th European Conference on Artificial Intelligence (ECAI), 8, (pp. 366–370).
Feigenbaum, I., & Sethuraman, J. (2014). Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location. arXiv preprint arXiv:1412.3414.
Feigenbaum, I., Sethuraman, J., & Ye, C. (2013). Approximately optimal mechanisms for strategyproof facility location: Minimizing \(l_p \) norm of costs. arXiv preprint arXiv:1305.2446.
Feldman, M., & Wilf, Y. (2013). Strategyproof facility location and the least squares objective. In Proceedings of the 14th ACM conference on Electronic Commerce (ACM-EC) (pp. 873–890).
Filos-Ratsikas, A., & Miltersen, P. B. (2014). Truthful approximations to range voting. In International Conference on Web and Internet Economics (pp. 175–188). Springer.
Fotakis, D., & Tzamos, C. (2010). Winner-imposing strategyproof mechanisms for multiple facility location games. In Proceeding of the 5th International Workshop of Internet and Network Economics (WINE) (pp. 234–245).
Fotakis, D., Tzamos, C., & Zampetakis, E. (2015). Who to trust for truthfully maximizing welfare? arXiv preprint arXiv:1507.02301.
Guo, M., & Conitzer, V. (2010). Strategy-proof allocation of multiple items between two agents without payments or priors. In Ninth International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS), Vol. 10, pp. 881–888.
Lu, P., Sun, X., Wang, Y., & Zhu, Z. A. (2010). Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM Conference on Electronic Commerce (ACM-EC) (pp. 315–324).
Lu, P., Wang, Y., & Zhou, Y. (2009). Tighter bounds for facility games. In Proceeding of the 5th International Workshop of Internet and Network Economics (WINE), (pp. 137–148).
Moulin, H. (1980). On strategy-proofness and single peakedness. Public Choice, 35(4), 437–455. CrossRef
Procaccia, A. D., Wajc, D., & Zhang, H. (2016). Approximation-Variance Tradeoffs in Mechanism Design. working paper.
Procaccia, A. D., & Tennenholtz, M. (2013). Approximate mechanism design without money. ACM Transactions on Economics and Computation, 1(4), 18. CrossRef
Rosen, H. S. (2005). Public Finance (7th ed.). McGraw-Hill Irwin.
Serafino, P., & Ventre, C. (2015). Truthful mechanisms without money for non-utilitarian heterogeneous facility location. In AAAI (pp. 1029–1035).
Sonoda, A., Todo, T., & Yokoo, M. (2016). False-name-proof locations of two facilities: Economic and algorithmic approaches. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, (pp. 615–621). AAAI Press.
Todo, T., Iwasaki, A., & Yokoo, M. (2011). False-name-proof mechanism design without money. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, (pp. 651–658). International Foundation for Autonomous Agents and Multiagent Systems.
Yang, Y., & Guo, J. (2015). How hard is control in multi-peaked elections: A parameterized study. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, (pp. 1729–1730). International Foundation for Autonomous Agents and Multiagent Systems.
Zou, S., & Li, M. (2015). Facility location games with dual preference. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, (pp. 615–623). International Foundation for Autonomous Agents and Multiagent Systems.
- Facility location with double-peaked preferences
- Springer US
Neuer Inhalt/© ITandMEDIA