Combinatorial auctions, where bidders can submit bids on bundles of items, are attractive when the bidders' valuations on bundles exhibit complementarity and/or substitutability. An important problem is that of eliciting the bidders' preferences so that they do not have to bid on all combinations. We present a new family of preference elicitation algorithms. The algorithms in this family do not rely on absolute bids, but rather on relative (differential) value information. This holds the promise to reduce revelation and communication significantly. We develop a differential-elicitation algorithm that finds the efficient allocation of items to the bidders, and as a side-effect, the Vickrey payments (which make truthful bidding incentive compatible). We also present two auction mechanisms that use differential elicitation.
展开▼
