Revenue maximization when bidders have budgets

We study the problem of maximizing revenue for auctions with multiple units of a good where bidders have hard budget constraints, first considered in 2. The revenue obtained by an auction is compared with the optimal omniscient auction had the auctioneer known the private information of all the bidders, as in competitive analysis 7. We show that the revenue of the optimal omniscient auction that sells items at many different prices is within a factor of 2 of the optimal omniscient auction that sells all the items at a single price, implying that our results will carry over to multiple price auctions. We give the first auction for this problem, to the best of our knowledge, that is known to obtain a constant fraction of the optimal revenue when the bidder dominance (the ratio between the maximum contribution of a single bidder in the optimal solution and the revenue of that optimal solution) is large (as high as 1/2). Our auction is also shown to remain truthful if canceled upon not meeting certain criteria. On the negative side, we show that no auction can achieve a guarantee of 1/2-e the revenue of the optimal omniscient multi-price auction. Finally, if the bidder dominance is known in advance and is less than 1/5.828, we give an auction mechanism that raises a large constant fraction of the optimal revenue when the bidder dominance is large and is asymptotically close to the optimal omniscient auction as the bidder dominance decreases. We discuss the relevance of these results for related applications.