Bayesian algorithmic mechanism design

Abstract

This article surveys recent work with an algorithmic flavor in Bayesian mechanism design. Bayesian mechanism design involves optimization in economic settings where the designer possesses some stochastic information about the input. Recent years have witnessed huge advances in our knowledge and understanding of algorithmic techniques for Bayesian mechanism design problems. These include, for example, revenue maximization in settings where buyers have multi-dimensional preferences, optimization of non-linear objectives such as makespan, and generic reductions from mechanism design to algorithm design. However, a number of tantalizing questions remain un-solved.

This article is meant to serve as an introduction to Bayesian mechanism design for a novice, as well as a starting point for a broader literature search for an experienced researcher.

References

1. Abraham, I., Athey, S., Babaioff, M., and Grubb, M. 2013. Peaches, lemons, and cookies: Designing auction markets with dispersed information. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce. EC '13. ACM, New York, NY, USA, 7--8.
2. Alaei, S. 2014. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing 43, 2, 930--972.
3. Alaei, S., Fu, H., Haghpanah, N., and Hartline, J. D. 2013. The simple economics of approximately optimal auctions. In IEEE Symp. on Foundations of Computer Science. 628--637.
4. Alaei, S., Fu, H., Haghpanah, N., Hartline, J. D., and Malekian, A. 2012. Bayesian optimal auctions via multi- to single-agent reduction. In ACM Conf. on Electronic Commerce. 17.
5. Ashlagi, I., Dobzinski, S., and Lavi, R. 2009. An optimal lower bound for anonymous scheduling mechanisms. In Proceedings of the 10th ACM Conference on Electronic Commerce. EC '09. 169--176.
6. Azar, P. D., Daskalakis, C., Micali, S., and Weinberg, S. M. 2013. Optimal and efficient parametric auctions. In ACM Symp. on Discrete Algorithms. 596--604.
7. Azar, P. D., Kleinberg, R., and Weinberg, S. M. 2014. Prophet inequalities with limited information. In ACM Symp. on Discrete Algorithms. 1358--1377.
8. Babaioff, M., Immorlica, N., Lucier, B., and Weinberg, S. M. 2014. A simple and approximately optimal mechanism for an additive buyer. arXiv:1405.6146.
9. Babaioff, M., Kleinberg, R., and Leme, R. P. 2012. Optimal mechanisms for selling information. In ACM Conf. on Electronic Commerce. 92--109.
10. Bei, X. and Huang, Z. 2011. Bayesian incentive compatibility via fractional assignments. In ACM Symp. on Discrete Algorithms. 720--733.
11. Bhalgat, A., Chakraborty, T., and Khanna, S. 2012. Mechanism design for a risk averse seller. In Workshop on Internet and Network Economics (WINE). 198--211.
12. Bhalgat, A., Gollapudi, S., and Munagala, K. 2013. Optimal auctions via the multiplicative weight method. In ACM Conf. on Electronic Commerce. 73--90.
13. Bhattacharya, S., Goel, G., Gollapudi, S., and Munagala, K. 2010. Budget constrained auctions with heterogeneous items. In ACM Symp. on Theory of Computing. 379--388.
14. Blumrosen, L. and Nisan, N. 2009. On the computational power of demand queries. SIAM J. Comput. 39, 4, 1372--1391.
15. Border, K. 2007. Reduced form auctions revisited. Economic Theory 31, 1, 167--181.
16. Border, K. C. 1991. Implementation of reduced form auctions: A geometric approach. Econometrica 59, 4, 1175--87.
17. Briest, P. 2008. Uniform budgets and the envy-free pricing problem. In ICALP. 808--819.
18. Briest, P., Chawla, S., Kleinberg, R., and Weinberg, S. M. 2014. Pricing randomized allocations. Journal of Economic Theory. To appear.
19. Brualdi, R. A. 1969. Comments on bases in dependence structures. Bulletin of the Australian Mathematical Society 1, 161--167.
20. Bulow, J. and Klemperer, P. 1996. Auctions vs negotiations. American Economic Review 86, 1, 180--194.
21. Bulow, J. and Roberts, J. 1989. The simple economics of optimal auctions. The Journal of Political Economy 97, 1060--90.
22. Cai, Y. and Daskalakis, C. 2011. Extreme-value theorems for optimal multidimensional pricing. In IEEE Symp. on Foundations of Computer Science. 522--531.
23. Cai, Y., Daskalakis, C., and Weinberg, S. M. 2012a. An algorithmic characterization of multi-dimensional mechanisms. In ACM Symp. on Theory of Computing. 459--478.
24. Cai, Y., Daskalakis, C., and Weinberg, S. M. 2012b. Optimal multidimensional mechanism design: Reducing revenue to welfare maximization. In IEEE Symp. on Foundations of Computer Science. 130--139.
25. Cai, Y., Daskalakis, C., and Weinberg, S. M. 2013a. Reducing revenue to welfare maximization: Approximation algorithms and other generalizations. In ACM Symp. on Discrete Algorithms. 578--595.
26. Cai, Y., Daskalakis, C., and Weinberg, S. M. 2013b. Understanding incentives: Mechanism design becomes algorithm design. In IEEE Symp. on Foundations of Computer Science. 618--627.
27. Cai, Y. and Huang, Z. 2013. Simple and nearly optimal multi-item auctions. In ACM Symp. on Discrete Algorithms. 564--577.
28. Chakraborty, T., Even-Dar, E., Guha, S., Mansour, Y., and Muthukrishnan, S. 2010. Approximation schemes for sequential posted pricing in multi-unit auctions. In WINE. 158--169.
29. Chawla, S., Fu, H., and Karlin, A. 2014. Approximate revenue maximization in interdependent value settings. In ACM Conf. on Electronic Commerce. To appear.
30. Chawla, S., Hartline, J. D., and Kleinberg, R. D. 2007. Algorithmic pricing via virtual valuations. In ACM Conf. on Electronic Commerce. 243--251.
31. Chawla, S., Hartline, J. D., Malec, D. L., and Sivan, B. 2010. Multi-parameter mechanism design and sequential posted pricing. In ACM Symp. on Theory of Computing. 311--320.
32. Chawla, S., Hartline, J. D., Malec, D. L., and Sivan, B. 2013. Prior-independent mechanisms for scheduling. In ACM Symp. on Theory of Computing. 51--60.
33. Chawla, S., Hartline, J. D., and Sivan, B. 2012. Optimal crowdsourcing contests. In ACM Symp. on Discrete Algorithms. 856--868.
34. Chawla, S., Immorlica, N., and Lucier, B. 2012. On the limits of black-box reductions in mechanism design. In ACM Symp. on Theory of Computing. 435--448.
35. Chawla, S., Malec, D. L., and Malekian, A. 2011. Bayesian mechanism design for budget-constrained agents. In ACM Conf. on Electronic Commerce. 253--262.
36. Chawla, S., Malec, D. L., and Sivan, B. 2012. The power of randomness in bayesian optimal mechanism design. Games and Economic Behavior. http://dx.doi.org/10.1016/j.geb.2012.08.010.
37. Che, Y.-K., Kim, J., and Mierendorff, K. 2013. Generalized reduced-form auctions: A network-flow approach. Econometrica 81, 6, 2487--2520.
38. Chen, X., Diakonikolas, I., Paparas, D., Sun, X., and Yannakakis, M. 2014. The complexity of optimal multidimensional pricing. In ACM Symp. on Discrete Algorithms. 1319--1328.
39. Chen, X., Hu, G., Lu, P., and Wang, L. 2011. On the approximation ratio of k-lookahead auction. In Workshop on Internet and Network Economics (WINE). 61--71.
40. Chung, K. and Ely, J. C. 2006. Ex-post incentive compatible mechanism design. Manuscript.
41. Cole, R. and Roughgarden, T. 2014. The sample complexity of revenue maximization. In ACM Symp. on Theory of Computing. To appear.
42. Constantin, F. and Parkes, D. C. 2009. Self-correcting sampling-based dynamic multi-unit auctions. In ACM Conf. on Electronic Commerce. 89--98.
43. Cremer, J. and McLean, R. P. 1988. Full Extraction of the Surplus in Bayesian and Dominant Strategy Auctions. Econometrica 56, 6 (November), 1247--57.
44. Csapó, G. and Müller, R. 2013. Optimal mechanism design for the private supply of a public good. Games and Economic Behavior 80, C, 229--242.
45. Daskalakis, C., Deckelbaum, A., and Tzamos, C. 2012. Optimal pricing is hard. In Workshop on Internet and Network Economics (WINE). 298--308.
46. Daskalakis, C., Deckelbaum, A., and Tzamos, C. 2013. Mechanism design via optimal transport. In ACM Conf. on Electronic Commerce. 269--286.
47. Daskalakis, C., Deckelbaum, A., and Tzamos, C. 2014. The complexity of optimal mechanism design. In ACM Symp. on Discrete Algorithms. 1302--1318.
48. Daskalakis, C. and Pierrakos, G. 2011. Simple, optimal and efficient auctions. In Workshop on Internet and Network Economics (WINE). 109--121.
49. Daskalakis, C. and Weinberg, S. M. 2014. Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms. arXiv:1405.5940.
50. Deb, R. and Pai, M. 2013. Ironing in dynamic revenue management: Posted prices & biased auctions. In ACM Symp. on Discrete Algorithms. 620--631.
51. Devanur, N. R., Hartline, J. D., Karlin, A. R., and Nguyen, C. T. 2011. Prior-independent multi-parameter mechanism design. In Workshop on Internet and Network Economics (WINE). 122--133.
52. Dhangwatnotai, P., Roughgarden, T., and Yan, Q. 2010. Revenue maximization with a single sample. In ACM Conf. on Electronic Commerce. 129--138.
53. Dobzinski, S., Fu, H., and Kleinberg, R. D. 2011. Optimal auctions with correlated bidders are easy. In ACM Symp. on Theory of Computing. 129--138.
54. Dobzinski, S. and Vondrak, J. 2012. The computational complexity of truthfulness in combinatorial auctions. In Proceedings of the 13th ACM Conference on Electronic Commerce. EC '12. ACM, New York, NY, USA, 405--422.
55. Dughmi, S., Immorlica, N., and Roth, A. 2014. Constrained signaling in auction design. In ACM Symp. on Discrete Algorithms. 1341--1357.
56. Dughmi, S. and Roughgarden, T. 2010. Black-box randomized reductions in algorithmic mechanism design. In FOCS. 775--784.
57. Emek, Y., Feldman, M., Gamzu, I., Leme, R. P., and Tennenholtz, M. 2012. Signaling schemes for revenue maximization. In ACM Conf. on Electronic Commerce. 514--531.
58. Fu, H., Haghpanah, N., Hartline, J., and Kleinberg, R. 2014. Optimal auctions for correlated bidders with sampling. In ACM Conf. on Electronic Commerce. To appear.
59. Fu, H., Hartline, J. D., and Hoy, D. 2013. Prior-independent auctions for risk-averse agents. In ACM Conf. on Electronic Commerce. 471--488.
60. Ghosh, A. and Kleinberg, R. 2014. Optimal contest design for simple agents. In ACM Conf. on Electronic Commerce. To appear.
61. Ghosh, A. and Roth, A. 2011. Selling privacy at auction. In Proceedings of the 12th ACM Conference on Electronic Commerce. EC '11. ACM, New York, NY, USA, 199--208.
62. Hart, S. and Nisan, N. 2012. Approximate revenue maximization with multiple items. In ACM Conf. on Electronic Commerce. 656.
63. Hart, S. and Nisan, N. 2013. The menu-size complexity of auctions. In ACM Conf. on Electronic Commerce. 565--566.
64. Hartline, J. D. 2013a. Bayesian mechanism design. Foundations and Trends in Theoretical Computer Science 8, 3, 143--263.
65. Hartline, J. D. 2013b. Mechanism design and approximation. http://jasonhartline.com/MDnA/.
66. Hartline, J. D., Kleinberg, R., and Malekian, A. 2011. Bayesian incentive compatibility via matchings. In ACM Symp. on Discrete Algorithms. 734--747.
67. Hartline, J. D. and Lucier, B. 2010. Bayesian algorithmic mechanism design. In ACM Symp. on Theory of Computing. 301--310.
68. Hartline, J. D. and Roughgarden, T. 2008. Optimal mechanism design and money burning. In ACM Symp. on Theory of Computing. 75--84.
69. Hartline, J. D. and Roughgarden, T. 2009. Simple versus optimal mechanisms. In ACM Conf. on Electronic Commerce. 225--234.
70. Huang, Z., Wang, L., and Zhou, Y. 2011. Black-box reductions in mechanism design. In Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 254--265.
71. Jehiel, P., Vehn, M. M.-t., Moldovanu, B., and Zame, W. R. 2006. The limits of ex post implementation. Econometrica 74, 3 (May), 585--610.
72. Kleinberg, R. and Weinberg, S. M. 2012. Matroid prophet inequalities. In ACM Symp. on Theory of Computing. 123--136.
73. Krishna, V. 2009. Auction theory. Academic press.
74. Li, X. and Yao, A. C.-C. 2013. On revenue maximization for selling multiple independently distributed items. Proceedings of the National Academy of Sciences.
75. Li, Y. 2013. Approximation in mechanism design with interdependent values. In ACM Conf. on Electronic Commerce. 675--676.
76. Manelli, A. and Vincent, D. 2007. Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly. Journal of Economic Theory 137, 1, 153--185.
77. Manelli, A. M. and Vincent, D. R. 2006. Bundling as an optimal selling mechanism for a multiple-good monopolist. Journal of Economic Theory 127, 1 (March), 1--35.
78. McAfee, R. P. and Reny, P. J. 1992. Correlated Information and Mechanism Design. Econometrica 60, 2 (March), 395--421.
79. Milgrom, P. R. and Weber, R. J. 1982. A Theory of Auctions and Competitive Bidding. Econometrica 50, 5 (September), 1089--1122.
80. Miltersen, P. B. and Sheffet, O. 2012. Send mixed signals: earn more, work less. In ACM Conf. on Electronic Commerce. 234--247.
81. Minooei, H. and Swamy, C. 2013. Near-optimal and robust mechanism design for covering problems with correlated players. In Conference on Web and Internet Economics (WINE). 377--390.
82. Myerson, R. 1981. Optimal auction design. Mathematics of Operations Research 6, 58--73.
83. Nisan, N. 2014. Algorithmic mechanism design (through the lens of multi-unit auctions). To appear in the Handbook of Game Theory, IV.
84. Nisan, N. and Ronen, A. 2001. Algorithmic mechanism design. Games and Economic Behavior 35, 1-2, 166--196.
85. Papadimitriou, C. H. and Pierrakos, G. 2011. On optimal single-item auctions. In ACM Symp. on Theory of Computing. 119--128.
86. Parkes, D. C. 2009. When analysis fails: Heuristic mechanism design via self-correcting procedures. In SOFSEM. 62--66.
87. Parkes, D. C. and Duong, Q. 2007. An ironing-based approach to adaptive online mechanism design in single-valued domains. In AAAI. 94--101.
88. Pavlov, G. 2011a. Optimal mechanism for selling two goods. The B.E. Journal of Theoretical Economics 11, 1.
89. Pavlov, G. 2011b. A property of solutions to linear monopoly problems. The B.E. Journal of Theoretical Economics 11, 4.
90. Riley, J. and Zeckhauser, R. 1983. Optimal Selling Strategies: When to Haggle, When to Hold Firm. The Quarterly Journal of Economics 98, 2 (May), 267--89.
91. Rochet, J.-C. 1987. A necessary and sufficient condition for rationalizability in a quasi-linear context. Journal of Mathematical Economics 16, 2 (April), 191--200.
92. Rochet, J.-C. and Chone, P. 1998. Ironing, Sweeping, and Multidimensional Screening. Econometrica 66, 4, 783--826.
93. Ronen, A. 2001. On approximating optimal auctions. In ACM Conf. on Electronic Commerce. 11--17.
94. Ronen, A. and Saberi, A. 2002. On the hardness of optimal auctions. In IEEE Symp. on Foundations of Computer Science. 396--405.
95. Roughgarden, T. and Talgam-Cohen, I. 2013. Optimal and near-optimal mechanism design with interdependent values. In ACM Conf. on Electronic Commerce. 767--784.
96. Roughgarden, T., Talgam-Cohen, I., and Yan, Q. 2012. Supply-limiting mechanisms. In ACM Conf. on Electronic Commerce. 844--861.
97. Samuel-Cahn, E. 1984. Comparison of threshold stop rules and maximum for independent nonnegative random variables. The Annals of Probability 12, 4, 1213--1216.
98. Sivan, B. and Syrgkanis, V. 2013. Vickrey auctions for irregular distributions. In Conference on Web and Internet Economics (WINE). 422--435.
99. Sundararajan, M. and Yan, Q. 2010. Robust mechanisms for risk-averse sellers. In ACM Conf. on Electronic Commerce. 139--148.
100. Syrgkanis, V., Kempe, D., and Tardos, E. 2013. Information asymmetries in common-value auctions with discrete signals. In SSRN.
101. Syrgkanis, V. and Tardos, E. 2013. Composable and efficient mechanisms. In ACM Symp. on Theory of Computing. 211--220.
102. Thanassoulis, J. E. 2004. Haggling Over Substitutes. Journal of Economic Theory 117, 2, 217--245.
103. Vohra, R. 2011. Mechanism design: A linear programming approach (Econometric society monographs). Cambridge University Press.
104. Wang, Z. and Tang, P. 2014. Optimal mechanisms with simple menus. In ACM Conf. on Electronic Commerce. To appear.
105. Wilson, R. 1969. Competitive bidding with disparate information. Management Sciences 15.
106. Yan, Q. 2011. Mechanism design via correlation gap. In ACM Symp. on Discrete Algorithms. 710--719.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Economics