A <b>combinatorial auction</b> is a type of market in which participants can place bids on combinations of discrete items, or ?packages?, rather than individual items or continuous quantities. Simple combinatorial auctions have been used for many years in estate auctions, where a common procedure is to accept bids for packages of items. They have been used recently for truckload transportation, bus routes, industrial procurement, and in the allocation of radio spectrum for wireless communications.<div>Combinatorial auctions present challenges compared to traditional auctions. Some challenges are computational, some economic, and some hybrid. An example of a computational problem is how to efficiently determine the allocation once the bids have been submitted to the auctioneer. This is called the winner determination problem.</div><div><br></div><div><br></div><div>It can be stated as follows: Given a set of bids in a combinatorial auction, find an allocation of items to bidders?including the possibility that the auctioneer retains some items?that maximizes the auctioneer?s revenue. This problem is difficult for large instances. Specifically, it is NP-hard, meaning that there is no known polynomial-time algorithm to find the optimal allocation.<br></div><div><br></div><div><a href="http://en.wikipedia.org/wiki/Combinatorial_auction">http://en.wikipedia.org/wiki/Combinatorial_auction</a><br></div>