Multi-unit auctions with budget-constrained bidders

• DOI: 10.1145/1064009.1064014
• Publication Date: 2005-08-03T04:31:47Z
• Authors: Christian Borgs; Jennifer Chayes; Nicole Immorlica; Mohammad Mahdian; Amin Saberi
• Keywords: Budget constraint; Mechanism Design

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