Asymptotically optimal strategy-proof mechanisms for two-facility games

ABSTRACT

We consider the problem of locating facilities in a metric space to serve a set of selfish agents. The cost of an agent is the distance between her own location and the nearest facility. The social cost is the total cost of the agents. We are interested in designing strategy-proof mechanisms without payment that have a small approximation ratio for social cost. A mechanism is a (possibly randomized) algorithm which maps the locations reported by the agents to the locations of the facilities. A mechanism is strategy-proof if no agent can benefit from misreporting her location in any configuration.

This setting was first studied by Procaccia and Tennenholtz [21]. They focused on the facility game where agents and facilities are located on the real line. Alon et al. studied the mechanisms for the facility games in a general metric space [1]. However, they focused on the games with only one facility. In this paper, we study the two-facility game in a general metric space, which extends both previous models.

We first prove an Ω(n) lower bound of the social cost approximation ratio for deterministic strategy-proof mechanisms. Our lower bound even holds for the line metric space. This significantly improves the previous constant lower bounds [21, 17]. Notice that there is a matching linear upper bound in the line metric space [21]. Next, we provide the first randomized strategy-proof mechanism with a constant approximation ratio of 4. Our mechanism works in general metric spaces. For randomized strategy-proof mechanisms, the previous best upper bound is O(n) which works only in the line metric space.

References

1. N. Alon, M. Feldman, A. D. Procaccia, and M. Tennenholtz. Strategyproof approximation mechanisms for location on networks. CoRR, abs/0907.2049, 2009.
2. A. Archer and É. Tardos. Truthful mechanisms for one-parameter agents. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 482--491, 2001.
3. S. Barberà. An introduction to strategy-proof social choice functions. Social Choice and Welfare, 18(4):619--653, 2001.
4. S. Barberà and M. Jackson. A characterization of strategy-proof social choice functions for economies with pure public goods. Social Choice and Welfare, 11(3):241--252, 1994.
5. S. Barbera and B. Peleg. Strategy-proof voting schemes with continuous preferences. Social Choice and Welfare, 7(1):31--38, 1990.
6. D. Black. On the rationale of group decision-making. The Journal of Political Economy, pages 23--34, 1948.
7. G. Christodoulou, E. Koutsoupias, and A. Vidali. A lower bound for scheduling mechanisms. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1163--1170, 2007.
8. E. H. Clarke. Multipart Pricing of Public Goods. Public Choice, 11:17--33, 1971.
9. O. Dekel, F. Fischer, and A.D. Procaccia. Incentive compatible regression learning. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 884--893, 2008.
10. P. Dhangwatnotai, S. Dobzinski, S. Dughmi, and T. Roughgarden. Truthful approximation schemes for single-parameter agents. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 15--24, 2008.
11. A. Gibbard. Manipulation of voting schemes: A general result. Econometrica, pages 587--601, 1973.
12. T. Groves. Incentives in Teams. Econometrica, 41:617--631, 1973.
13. E. Koutsoupias and A. Vidali. A lower bound of 1 + φ for truthful scheduling mechanisms. In Proceedings of the 32nd International Symposium of Mathematical Foundations of Computer Science (MFCS), pages 454--464, 2007.
14. R. Lavi and C. Swamy. Truthful and near-optimal mechanism design via linear programming. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 595--604, 2005.
15. D. Lehmann, L. I. Oćallaghan, and Y. Shoham. Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM, 49(5):577--602, 2002.
16. P. Lu. On 2-player randomized mechanisms for scheduling. In Proceedings of the 5th International Workshop of Internet and Network Economics (WINE), pages 30--41, 2009.
17. P. Lu, Y. Wang, and Y. Zhou. Tighter bounds for facility games. In Proceedings of the 5th International Workshop of Internet and Network Economics (WINE), pages 137--148, 2009.
18. P. Lu and C. Yu. Randomized truthful mechanisms for scheduling unrelated machines. In Proceedings of the 4th International Workshop of Internet and Network Economics (WINE), pages 402--413, 2008.
19. H. Moulin. On strategy-proofness and single peakedness. Public Choice, 35(4):437--455, 1980.
20. N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1-2):166--196, 2001.
21. A. D. Procaccia and M. Tennenholtz. Approximate mechanism design without money. In Proceedings of the 10th ACM Conference on Electronic Commerce (ACM-EC), 2009.
22. M. A. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2):187--217, 1975.
23. J. Schummer and R. V. Vohra. Strategy-proof location on a network. Journal of Economic Theory, 104, 2001.
24. J. Schummer and R. V. Vohra. Mechanism design without money, chapter 10. Cambridge University Press, 2007.
25. Y. Sprumont. The division problem with single-peaked preferences: a characterization of the uniform allocation rule. Econometrica, pages 509--519, 1991.
26. W. Vickrey. Counterspeculation, Auctions, and Competitive Sealed Tenders. Journal of Finance, 16:8--37, 1961.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Economics

• Theory of computation

  • Design and analysis of algorithms