A Caltech Library Service

Optimal Combinatoric Auctions with Single-Minded Bidders

Ledyard, John O. (2007) Optimal Combinatoric Auctions with Single-Minded Bidders. In: Proceedings of the 8th ACM conference on Electronic commerce. Association for Computing Machinery , pp. 237-242. ISBN 978-1-59593-653-0.

[img] PDF - Published Version
Restricted to Repository administrators only
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2007 ACM. Year of Publication: 2007 I would like to thank the significant help of several referees in catching typos and adding references.
Subject Keywords:combinatoric auctions; mechanism design; core
Record Number:CaltechAUTHORS:20100924-103442954
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:20122
Deposited On:24 Sep 2010 20:14
Last Modified:08 Nov 2021 23:57

Repository Staff Only: item control page