Multi-unit Auctions with Budget-constrained Bidders

We study a multi-unit auction with multiple agents, each of whom has a private valuation and budget. The truthful mechanisms of such an auction are characterized, in the sense that, under standard assumptions, we prove that it is impossible to design a non-trivial truthful auction which allocates all items, while we provide the design of an asymptotically revenue-maximizing truthful mechanism which may allocate only some of the items. Our asymptotic parameter is a budget dominance parameter which measures the size of the budget of a single agent relative to the maximum revenue. We discuss the relevance of these results for the design of online ad auctions.