Budget feasible mechanisms for facility location games with strategic facilities

1. Amanatidis, G., Birmpas, G., & Markakis, E. (2017). On budget-feasible mechanism design for symmetric submodular objectives. In Proceedings of the 13th international conference on web and internet economics (WINE), pp. 1–15.

2. Archer, A., & Tardos, É. (2001). Truthful mechanisms for one-parameter agents. In Proceedings 42nd IEEE symposium on foundations of computer science (FOCS), pp. 482–491.

3. Aziz, H., Chan, H., Lee, B.E., & Parkes, D.C. (2019). The capacity constrained facility location problem. In Proceedings of the 15th international conference on web and internet economics (WINE), pp. 336.

4. Babaioff, M., Feldman, M., & Tennenholtz, M. (2016). Mechanism design with strategic mediators. ACM Transactions on Economics and Computation, 4(2), 1–48.

   Article  MathSciNet  MATH  Google Scholar 

5. Balkanski, E., Garimidi, P., Gkatzelis, V., Schoepflin, D., & Tan, X. (2022). Deterministic budget-feasible clock auctions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2940–2963.

6. Bei, X., Chen, N., Gravin, N., & Lu, P. (2012). Budget feasible mechanism design: from prior-free to bayesian. In Proceedings of the 44th annual ACM symposium on theory of computing (STOC), pp. 449–458.

7. Chan, H., Filos-Ratsikas, A., Li, B., Li, M., & Wang, C. (2021). Mechanism design for facility location problems: a survey. In Proceedings of the 30th international joint conference on artificial intelligence (IJCAI), pp. 4356–4365.

8. Chen, N., Gravin, N., & Lu, P. (2011). On the approximability of budget feasible mechanisms. In Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 685–699.

9. Chen, X., Li, M., Wang, C., Wang, C., & Zhao, Y. (2019). Truthful mechanisms for location games of dual-role facilities. In Proceedings of the 18th international conference on autonomous agents and multiagent systems (AAMAS), pp. 1470–1478.

10. Cheng, Y., Wei, Yu., & Zhang, G. (2013). Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Computer Science, 497, 154–163.

    Article  MathSciNet  MATH  Google Scholar 

11. Feigenbaum, I., Sethuraman, J., & Ye, C. (2017). Approximately optimal mechanisms for strategyproof facility location: Minimizing \(l_p\) norm of costs. Mathematics of Operations Research, 42(2), 434–447.

    Article  MathSciNet  MATH  Google Scholar 

12. Feldman, M., Fiat, A., & Golomb, I. (2016). On voting and facility location. In Proceedings of the 17th ACM conference on economics and computation (EC), pp. 269–286.

13. Feldman, M. & Wilf Y. (2013). Strategyproof facility location and the least squares objective. In Proceedings of the 14th ACM conference on electronic commerce (EC), pp. 873–890.

14. Filos-Ratsikas, A., Li, M., Zhang, J., & Zhang, Q. (2017). Facility location with double-peaked preferences. Autonomous Agents and Multi-Agent Systems, 31(6), 1209–1235.

    Article  Google Scholar 

15. Fotakis, D., & Tzamos, C. (2014). On the power of deterministic mechanisms for facility location games. ACM Transactions on Economics and Computation, 2(4), 15.

    Article  MATH  Google Scholar 

16. Jalaly Khalilabadi, P. & Tardos, É. (2018). Simple and efficient budget feasible mechanisms for monotone submodular valuations. In Proceedings of the 14th international conference on web and internet economics (WINE), pp. 246–263.

17. Leonardi, S., Monaco, G., Sankowski, P., & Zhang, Q. (2017). Budget feasible mechanisms on matroids. In International conference on integer programming and combinatorial optimization, pp. 368–379.

18. Li, M., Wang, C., & Zhang, M. (2020). Budgeted facility location games with strategic facilities. In Proceedings of the 29th international joint conference on artificial intelligence (IJCAI), pp. 400–406.

19. 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 (EC), pp. 315–324.

20. Moulin, H. (1980). On strategy-proofness and single peakedness. Public Choice, 35(4), 437–455.

    Article  Google Scholar 

21. Myerson, R. B. (1981). Optimal auction design. Mathematics of Operations Research, 6(1), 58–73.

    Article  MathSciNet  MATH  Google Scholar 

22. Nisan, N., & Ronen, A. (2001). Algorithmic mechanism design. Games and Economic Behavior, 35(1–2), 166–196.

    Article  MathSciNet  MATH  Google Scholar 

23. Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. V. (2007). Algorithmic game theory. Cambridge: Cambridge University Press.

    Book  MATH  Google Scholar 

24. Procaccia, A.D. & Tennenholtz, M. (2009). Approximate mechanism design without money. In Proceedings of the 10th ACM conference on electronic commerce, pp. 177–186.

25. Schummer, J., & Vohra, R. V. (2002). Strategy-proof location on a network. Journal of Economic Theory, 104(2), 405–428.

    Article  MathSciNet  MATH  Google Scholar 

26. Paolo, S. & Ventre, C. (2015). Truthful mechanisms without money for non-utilitarian heterogeneous facility location. In Proceedings of the 29th conference on artificial intelligence (AAAI), pp. 1029–1035.

27. Serafino, P., Ventre, C., & Vidali, A. (2020). Truthfulness on a budget: trading money for approximation through monitoring. Autonomous Agents and Multi-Agent Systems, 34(1), 1–24.

    Article  Google Scholar 

28. Singer, Y. (2010). Budget feasible mechanisms. In Proceedings 51st IEEE symposium on foundations of computer science (FOCS), pp. 765–774.

29. Wada, Y., Ono, T., Todo, T., & Yokoo, M. (2018). Facility location with variable and dynamic populations. In Proceedings of the 17th international conference on autonomous agents and multiagent systems (AAMAS), pp. 336–344.

30. Yao, A.C.-C. (1977). Probabilistic computations: Toward a unified measure of complexity. In Proceedings 18th IEEE symposium on foundations of computer science (FOCS), pp. 222–227.

Download references