Computer Science Department
School of Computer Science, Carnegie Mellon University
Effectiveness of Preference Elicitation in Combinatorial Auctions
Benoit Hudson, Tuomas Sandholm
Keywords: Combinatorial auction, preference elicitation
Combinatorial auctions where agents can bid on bundles of items
are desirable be-cause they allow the agents to express
complementarity and substitutability between the items. However,
expressing one s preferences can require bidding on all bundles.
Selective incremental preference elicitation by the auctioneer was recently
proposed to address this problem, but the idea was not
evaluated. In this paper we show, experimentally and theoretically,
that automated elicitation provides a drastic benefit. In all
of the elicitation schemes under study, as the number of items
for sale increases, the amount of information elicited is a
vanishing fraction of the information collected in traditional
direct revelation mechanisms where bidders reveal all their
valuation information. Most of the elicitation schemes also
maintain the benefit as the number of agents increases. We develop
more effective elicitation policies for existing query types.
We also present a new query type that takes the incremental nature
of elicitation to a new level by allowing agents to give
approximate answers that are refined only on an as-needed basis.
In the process, we present methods for evaluating different types
of elicitation policies.