Revenue Maximizing Envy-free Multi-unit Auctions with Budgets

Stefano Leonardi ( Sapienza University of Rome )

We study envy-free mechanisms for multi-unit auctions with budgeted agents that approximately maximize revenue. In an envy-free auction, prices are set so that every bidder receives a bundle that maximizes her utility amongst all bundles. We study several variants of this problem. We present an auction that charges a fix price for each unit of a bundle that runs in polynomial time and provides a approximation of 1/2 with respect to the revenue-maximizing auction. However, we also show the existence of an FPTAS if we compare against an optimal fix-price auction. Unit demand auctions, multi-unit auctions with matching preference constraints and several open problems will also be discussed.