Optimal Combinatoric Auctions with Single-Minded Bidders

Abstract

Combinatoric auctions sell K objects to N people who have preferences defined on subsets of the items. The optimal auction satisfies incentive compatibility (it is a dominant strategy to report true values), voluntary participation (bidders are not worse off through participation) and maximizes the expected revenue of the auctioneer among such auctions. In this paper, the optmal auction is characterized for the special case of single-minded bidders. It is shown that the optimal auction is not a Vickrey-Clarke-Groves mechanism. The optimal auction uses pivot prices, as in VCG, but it also uses bidder preferences. An example is provided showing improvement over the VCG mechanism can be large. The example also illustrates that auctions that are efficient or in the core are not optimal.

Additional details