Bayesian Budget Feasibility with Posted Pricing

ABSTRACT

We consider the problem of budget feasible mechanism design proposed by Singer, but in a Bayesian setting. A principal has a public value for hiring a subset of the agents and a budget, while the agents have private costs for being hired. We consider both additive and submodular value functions of the principal. We show that there are simple, practical, ex post budget balanced posted pricing mechanisms that approximate the value obtained by the Bayesian optimal mechanism that is budget balanced only in expectation. A main motivating application for this work is crowdsourcing, e.g., on Mechanical Turk, where workers are drawn from a large population and posted pricing is standard. Our analysis methods relate to contention resolution schemes in submodular optimization of Vondràk et al. and the correlation gap analysis of Yan.

References

1. S. Agrawal, Y. Ding, A. Saberi, and Y. Ye. Correlation robust stochastic optimization. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1087--1096. Society for Industrial and Applied Mathematics, 2010.
2. S. Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing, 43(2):930--972, 2014.
3. N. Anari, G. Goel, and A. Nikzad. Mechanism design for crowdsourcing: An optimal 1--1/e competitive budget-feasible mechanism for large markets. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 266--275. IEEE, 2014.
4. A. Badanidiyuru, R. Kleinberg, and Y. Singer. Learning on a budget: posted price mechanisms for online procurement. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 128--145. ACM, 2012.
5. N. Bansal, N. Korula, V. Nagarajan, and A. Srinivasan. On k-column sparse packing programs. In Integer Programming and Combinatorial Optimization, pages 369--382. Springer, 2010.
6. X. Bei, N. Chen, N. Gravin, and P. Lu. Budget feasible mechanism design: from prior-free to bayesian. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 449--458. ACM, 2012.
7. J. Bulow and J. Roberts. The simple economics of optimal auctions. The Journal of Political Economy, pages 1060--1090, 1989.
8. G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a submodular set function subject to a matroid constraint. In Integer programming and combinatorial optimization, pages 182--196. Springer, 2007.
9. G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6):1740--1766, 2011.
10. S. Chawla, J. D. Hartline, D. L. Malec, and B. Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM Symposium on Theory of Computing, pages 311--320. ACM, 2010.
11. S. Chawla, J. D. Hartline, and B. Sivan. Optimal crowdsourcing contests. In Proceedings of the twenty-third annual ACM-SIAM symposium on discrete algorithms, pages 856--868. SIAM, 2012.
12. N. Chen, N. Gravin, and P. Lu. On the approximability of budget feasible mechanisms. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 685--699. SIAM, 2011.
13. N. R. Devanur, B. Q. Ha, and J. D. Hartline. Prior-free auctions for budgeted agents. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pages 287--304. ACM, 2013.
14. L. Ensthaler and T. Giebe. Bayesian optimal knapsack procurement. European Journal of Operational Research, 234(3):774--779, 2014.
15. P. Esö and G. Futo. Auction design with a risk averse seller. Economics Letters, 65(1):71--74, 1999.
16. C.-J. Ho, A. Slivkins, S. Suri, and J. W. Vaughan. Incentivizing high quality crowdwork. In Proceedings of the 24th International Conference on World Wide Web, pages 419--429. International World Wide Web Conferences Steering Committee, 2015.
17. N. Immorlica, G. Stoddard, and V. Syrgkanis. Social status and badge design. In Proceedings of the 24th International Conference on World Wide Web, pages 473--483. International World Wide Web Conferences Steering Committee, 2015.
18. S. Khuller, A. Moss, and J. S. Naor. The budgeted maximum coverage problem. Information Processing Letters, 70(1):39--45, 1999.
19. R. Myerson. Optimal auction design. Mathematics of Operations Research, 6:58--73, 1981.
20. R. Myerson and M. Satterthwaite. Efficient mechanisms for bilaterial trade. Journal of Economic Theory, 29:265--281, 1983.
21. G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functionsâi. Mathematical Programming, 14(1):265--294, 1978.
22. Y. Singer. Budget feasible mechanisms. In The 51st Annual IEEE Symposium on Foundations of Computer Science, pages 765--774. IEEE, 2010.
23. Y. Singer and M. Mittal. Pricing mechanisms for crowdsourcing markets. In Proceedings of the 22nd international conference on World Wide Web, pages 1157--1166. International World Wide Web Conferences Steering Committee, 2013.
24. A. Singla and A. Krause. Truthful incentives in crowdsourcing tasks using regret minimization mechanisms. In Proceedings of the 22nd international conference on World Wide Web, pages 1167--1178. International World Wide Web Conferences Steering Committee, 2013.
25. M. Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41--43, 2004.
26. J. Vondrák, C. Chekuri, and R. Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 783--792. ACM, 2011.
27. Q. Yan. Mechanism design via correlation gap. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 710--719. SIAM, 2011.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Economics

• Theory of computation

  • Design and analysis of algorithms