Approximation Randomized Strategy-Proof Mechanisms in Obnoxious Facility Game with Weighted Agents
Tóm tắt
In this paper, we investigate the obnoxious facility location game with weighted agents. First, we design a randomized group strategy-proof mechanism with approximation ratio
$$\frac{3W_\mathrm{max}}{2W_\mathrm{min}}$$
when the weighted agents are located on a line; then, on the cycle metric, we also discuss the strategy-proofness and the approximation ratios of a class of group strategy-proof deterministic mechanisms.
Tài liệu tham khảo
Clarke, E.H.: Multipart pricing of public goods. Public Choice 11(1), 17–33 (1971)
Groves, T.: Incentives in teams. Econometrica 41(4), 617–631 (1973)
Vickrey, W.: Counter speculation, auctions, and competitive sealed tenders. J. Financ. 16(1), 8–37 (1961)
Moulin, H.: On strategy-proofness and single peakedness. Public Choice 35(4), 437–455 (1980)
Barbera, S., Berga, D., Moreno, B.: Domains, ranges and strategy-proofness: the case of single-dipped preferences. Soc. Choice Welf. 39(12), 335–352 (2012)
Border, K.C., Jordan, J.S.: Straightforward elections, unanimity and phantom voters. Rev. Econ. Stud. 50(1), 153–170 (1983)
Manjunath, V.: Efficient and strategy-proof social choice when preferences are single-dipped. Int. J. Game Theory 43(3), 579–597 (2014)
Nehring, K., Puppe, C.: The structure of strategy-proof social choice. Part I: general characterization and possibility results on median spaces. J. Econ. Theory 135(1), 269–305 (2007)
Nehring, K., Puppe, C.: Efficient and strategy-proof voting rules: a characterization. Games Econ. Behav. 59(1), 132–153 (2007)
Öztürk, M., Peters, H., Storcken, T.: Strategy-proof location of a public bad on a disc. Econ. Lett. 119(1), 14–16 (2013)
Öztürk, M., Peters, H., Storcken, T.: On the location of public bads: strategy-proofness under two-dimensional single-dipped preferences. Econ. Theory 56(1), 83–108 (2014)
Procaccia, A., Tennenholtz, M.: Approximate mechanism design without money. In: 10th Association for Computing Machinery Conference on Electronic Commerce, pp. 177–186. ACM, New York (2009)
Alon, N., Feldman, M., Procaccia, A., Tennenholtz, M.: Strategyproof Approximation Mechanisms for Location on Networks. Computing Research Repository-CORR arXiv:0907.2049 (2009)
Alon, N., Feldman, M., Procaccia, A., Tennenholtz, M.: Strategyproof approximation of the minimax on networks. Math. Oper. Res. 35(3), 513–526 (2010)
Lu, P., Wang, Y., Zhou, Y.: Asymptotically optimal strategy-proof mechanisms for two-facility games. In: 11th ACM Conference on Electronic Commerce, pp. 315–324. ACM, New York (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)
Cheng, Y.-K., Yu, W., Zhang, G.-C.: Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theor. Comput. Sci. 497, 154–163 (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)
Cheng, Y.-K., Zhou, S.-M.: A survey on approximation mechanism design without money for facility games. Advances in Global Optimization. Springer Proceedings in Mathematics and Statistics 95, 117–128 (2015)
Zhang, Q., Li, M.-M.: Strategyproof mechanism design for facility location games with weighted agents on a line. J. Comb. Optim. 28(4), 756–773 (2013)
Church, R.L., Garfinkel, R.S.: Locating an obnoxious facility on a network. Transp. Sci. 12(2), 107–118 (1978)
Tamir, A.: Obnoxious facility location on graphs. SIAM J. Discret. Math. 4(4), 550–567 (1991)
Ting, S.S.: A linear-time algorithm for maxisum facility location on tree networks. Transp. Sci. 18(1), 76–84 (1984)