Budget-Constrained Auctions

Deeparnab Chakrabarty (Vijay Vazirani) - We are interested in the following revenue maximization problem for an auctioneer: Given a set of indivisible items on which bidders bid on, how to allocate these items to the bidders so as to maximize the total revenue obtained. Apart from the bids, the bidders also specify a budget constraint which is the maximum the auctioneer can charge the bidder.

Examples of such budget-constrained auctions include those used for the privatization of public assets in western Europe, or those for the distribution of radio spectra in the US, where the magnitude of the transactions involved put nancial or liquidity constraints on bidders. More recently, the ad-auctions hosted by search engine companies are notable examples of budget-constrained auctions.