problem can be solved in polynomial time. 23 For example, if bidders bid only on bundles of at most two items, then the winner determination problem can be solved in polynomial time, via matching algorithms. In general, the runtime heavily depends on how the bids are generated: in some cases, it is possible to scale to hundreds of thousands of items and tens of thousands of bids, whereas in other cases, current techniques have trouble scaling beyond tens of items and hundreds of bids. 30

Instead of letting bidders bid only
once—that is, requiring them to give all
their valuation information at once—it
ently computational question: how
should the procedure for querying the
bidders be designed to minimize the re-
quired amount of communication?

is possible to use an iterative (or pref-
erence elicitation) format, in which
bidders repeatedly respond to queries
about their valuations. 25, 32 In a single-
item setting, this corresponds to the dis-
tinction between a sealed-bid auction,
in which each bidder bids only once, and
an English auction, in which the auc-
tioneer repeatedly queries the bidders
for higher valuations. Using preference
elicitation in a combinatorial auction
has the potential to greatly decrease the
total amount of valuation information
that the bidders need to communicate,
while still finding the efficient alloca-
tion. This leads to the following inher-
ing search engines to allocate the ad-
vertising space on their search results
pages. This is another example of an
auction with multiple resources for
sale: any search performed by a user
results in multiple advertisement slots
becoming available. These auctions are
called sponsored search auctions, and
they introduce a variety of new issues.
For example, in a typical sponsored
search auction, an advertiser pays only
if the user clicks on her ad, rather than
every time her ad is displayed. The
prominent place sponsored search
auctions occupy in the business mod-
els of the companies that use them has
helped to bring about an explosion of
research on them in recent years; 19 a
thorough discussion would easily mer-
it its own article.