Budget Constrained Auctions with Heterogeneous Items

Preprint
Abstract
In this paper, we consider the design of revenue-optimal, Bayesian incentive compatible mechanisms for auctioning multiple (heterogeneous) items, when bidders have a constraint on the amount of money they are willing to spend. Our focus is on designing mechanisms that approximate the optimal revenue and that can be computed in time polynomial in the number of bidders and items. We present constant factor approximations to three important and canonical special cases: (1) All-pay auctions, which we show approximate the optimal Bayesian incentive compatible mechanism to a constant factor when the type space of each bidder is discrete and types are directly revealed; (2) Covering auctions where the subset of items a bidder obtains has a certain influence which the bidder is interested in maximizing; and (3) Posted price auctions where the auctioneer can adaptively post different prices for different (bidder, item) pairs. For all these problems, our approach is based on formulating a poly-sized LP relaxation of the optimal incentive compatible mechanism, followed by rounding this solution to a feasible mechanism based on ideas from stochastic packing. The resulting auctions are practical and simple to implement.