Using value queries in combinatorial auctions

Combinatorial auctions, where bidders can bid on bundles of items, are known to be desirable auction mechanisms for selling items that are complementary and/or substitutable. However, there are 2^k --1 bundles, and each agent may need to bid on all of them to fully express its preferences. We address this by showing how them auctioneer can recommend to the agents incrementally which bundles to bid on so that they need to only place a small fraction of all possible bids. These algorithms impose a great computational burden on the auctioneer; we show how to speed them up dramatically. We also present an optimal elicitor, which is intractable but may be the basis for future algorithms. Finally, we introduce the notion of a universal revelation reducer, demonstrate a randomized one, and prove that no deterministic one exists.The full paper is available in draft form at http://www.cs.cmu.edu/ sandholm/using_value_queries.pdf.