Computer Science Department
School of Computer Science, Carnegie Mellon University
Random Sampling Auctions for Limited Supply
Maria-Florina Balcan, Nikhil Devanur*
Balcan et al.  show that the framework of the random sampling auction of Goldberg et al.  gives a generic reduction in the context of unlimited supply profit maximization from mechanism design (e.g., Goldberg et al. ) to algorithm design (e.g., Guruswami et al. ). One major open question left in  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  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.
*College of Computing, Georgia Institute of Technology