Theory Day March 2, 2009 - Noam Nisan

Multi-unit Auctions with Budget Limits

We study multi-unit auctions where the bidders have a budget constraint, a situation very common in practice that has received very little attention in the auction theory literature. Our main result is an impossibility: there are no incentive-compatible auctions that always produce a Pareto-optimal allocation. We also obtain some surprising positive results for the case of publicly-known budgets.

Joint work with Shahar Dobzinski and Ron Lavi.