Balcan et al. [3] show that the framework of the random sampling auction of Goldberg et al. [12] gives a generic reduction in the context of unlimited supply profit maximization from mechanism design (e.g., Goldberg et al. [12]) to algorithm design (e.g., Guruswami et al. [14]). One major open question left in [3] is to extend the results to limited supply settings. For the case that the seller has a large but limited supply of each commodity, we answer this question by giving a non-trivial adaptation of the random sampling auction framework to the limited supply setting, and prove bounds analogous to those of [3] for both the objectives of profit maximization and welfare maximization. These results generalize the prior work on random sampling limited supply auctions of Borgs et al. and Abrams [5, 1] which consider the special case where agents have linear valuations and budgets.

17 pages

*College of Computing, Georgia Institute of Technology
**Microsoft Research, Mountain View, CA

[1] Z. Abrams. Revenue Maximization When Bidders Have Budgets. 2006
[3] M.-F. Balcan, A. Blum, J. Hartline, and Y. Mansour. Mechanism Design via Machine Learning. 2005
[5] C. Borgs, J. T. Chayes, N. Immorlica, M. Mahdian, and A. Saberi. Multi-unit auctions with budget constrained bidders. 2005
[12] A. Goldberg, J. Hartline, and A. Wright. Competitive Auctions and Digital Goods. 2001
[14] V. Guruswami, J. Hartline, A. Karlin, D. Kempe, C. Kenyon, and F. McSherry. On Profit-Maximizing Envy-Free Pricing. 2005

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]