Multi-unit Auctions with Budget-constrained Bidders - Borgs, Christian; Chayes, Jennifer; Immorlica, Nicole; Mahdian, Mohammad; Saberi, Amin (Proceedings of the 6th ACM Conference on Electronic Commerce (EC), 2005)
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.