  Combinatorial auctions where agents can bid on bundles of items are desirable
because 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 (Conen & Sandholm 2001), 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.
